hiho week 21 register

Ended

Participants:248

Verdict:Accepted
Score:100 / 100
Submitted:2014-11-27 22:39:51

Lang:G++

Edit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int const N = 2e5 + 10;
vector <int> xs, cs;
vector <pair<int,int> > seg;
struct segmentTree {
    vector <int> color;
    segmentTree():color(N<<2, -1) {}
    void modify(int r, int L, int R, int a, int b, int c) {
        if (R < a || L > b || L > R) return;
        if (a <= L && R <= b) {
            color[r] = c;
        } else {
            int M = (L + R) >> 1, ls = r << 1, rs = ls | 1;
            if (color[r] != -1) {
                color[ls] = color[rs] = color[r];
                color[r] = -1;
            }
            modify(ls, L, M, a, b, c);
            modify(rs, M+1, R, a, b, c);
            if (color[ls] == color[rs]) color[r] = color[ls];
            else color[r] = -1;
        }
    }
    void query(int r, int L, int R) {
        if (color[r] != -1) {
            cs.push_back(color[r]);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX