oj.uz

Submission #124678

# Submission time Handle Problem Language Result Execution time Memory
124678 2019-07-03T17:14:48 Z EntityIT Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3532 ms 135828 KB 
/*
check long long - int
check N
*/
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = (int)3e5 + 5, Q = N;
int n, q;
string initSate;

struct Query {
    int t, a, b;
    Query (int _t = 0, int _a = 0, int _b = 0) : t(_t), a(_a), b(_b) {}
} query[Q];

struct Bit {
    static const int LOG = __lg(N) + 1;
    int a[1 << LOG];
    void init () { memset(a, 0, sizeof a); }
    void update (int pos, int val) {
        for (; pos < (1 << LOG); pos += pos & -pos) a[pos] += val;
    }
    int get (int pos) {
        int ret = 0;
        for (; pos > 0; pos -= pos & -pos) ret += a[pos];
        return ret;
    }
    int findPos (int val) {
        if (!val) return 0;
        int ret = 0;
        for (int i = LOG - 1; i >= 0; --i) if (a[ret | (1 << i)] < val) ret |= (1 << i), val -= a[ret];
        return min(ret, n) + 1;
    }
} bit;

struct Bit2D {
    vector<int> cmprssNmbr[N];
    vector<long long> a[N];
    void init () {
        for (int i = 0; i < N; ++i) cmprssNmbr[i].assign(1, -1);
    }
    void add (int x, int y) {
        for (; x < N; x += x & -x) {
            cmprssNmbr[x].pb(y);
        }
    }
    void interPhase () {
        for (int i = 1; i < N; ++i) {
            sort(cmprssNmbr[i].begin(), cmprssNmbr[i].end() );
            cmprssNmbr[i].erase(unique(cmprssNmbr[i].begin(), cmprssNmbr[i].end() ), cmprssNmbr[i].end() );
            a[i].assign(cmprssNmbr[i].size(), 0);
        }
    }
    void update (int x, int y, int val) {
        for (; x < N; x += x & -x) {
            int _y = (int)(lower_bound(cmprssNmbr[x].begin(), cmprssNmbr[x].end(), y) - cmprssNmbr[x].begin() );
            for (; _y < (int)a[x].size(); _y += _y & -_y) a[x][_y] += val;
        }
    }
    long long get (int x, int y) {
        long long ret = 0;
        for (; x > 0; x -= x & -x) {
            int _y = (int)(upper_bound(cmprssNmbr[x].begin(), cmprssNmbr[x].end(), y) - cmprssNmbr[x].begin() - 1);
            for (; _y > 0; _y -= _y & -_y) ret += a[x][_y];
        }
        return ret;
    }
    void update (int x1, int y1, int x2, int y2, int val) {
        update(x1, y1, val);
        update(x2 + 1, y2 + 1, val);
        update(x1, y2 + 1, -val);
        update(x2 + 1, y1, -val);
    }
} bit2D;

int32_t main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("test.INP", "r", stdin);

    bit2D.init();

    cin >> n >> q >> initSate; initSate = '!' + initSate;
    for (int i = 1; i <= q; ++i) {
        string str; cin >> str;
        if (str == "toggle") {
            int a; cin >> a;
            query[i] = Query(1, a, 0);
        }
        else {
            int a, b; cin >> a >> b; --b;
            query[i] = Query(2, a, b);
        }
    }

    string curState = initSate;
    for (int i = 1; i <= n; ++i) if (curState[i] == '0') bit.update(i, 1);

    for (int i = 0; i <= n; ++i) if (curState[i] != '1') {
        int j = bit.findPos(bit.get(i) + 1);
        if (i + 1 <= j - 1) {
            bit2D.add(i + 1, i + 1);
            bit2D.add(j, j);
            bit2D.add(i + 1, j);
            bit2D.add(j, i + 1);
        }
    }

    for (int i = 1; i <= q; ++i) if (query[i].t == 1) {
        if (curState[ query[i].a ] == '1') {
            curState[ query[i].a ] = '0';
            int l = bit.findPos(bit.get(query[i].a) ) + 1,
                r = bit.findPos(bit.get(query[i].a) + 1) - 1;
            bit2D.add(l, query[i].a);
            bit2D.add(query[i].a + 1, r + 1);
            bit2D.add(l, r + 1);
            bit2D.add(query[i].a + 1, query[i].a);
            bit.update(query[i].a, 1);
        }
        else {
            curState[ query[i].a ] = '1';
            int l = bit.findPos(bit.get(query[i].a) - 1 ) + 1,
                r = bit.findPos(bit.get(query[i].a) + 1) - 1;
            bit2D.add(l, query[i].a);
            bit2D.add(query[i].a + 1, r + 1);
            bit2D.add(l, r + 1);
            bit2D.add(query[i].a + 1, query[i].a);
            bit.update(query[i].a, -1);
        }
    }

    bit.init();
    bit2D.interPhase();

    curState = initSate;
    for (int i = 1; i <= n; ++i) if (curState[i] == '0') bit.update(i, 1);

    for (int i = 1; i <= q; ++i) {
        if (query[i].t == 1) {
            if (curState[ query[i].a ] == '1') {
                curState[ query[i].a ] = '0';
                int l = bit.findPos(bit.get(query[i].a) ) + 1,
                    r = bit.findPos(bit.get(query[i].a) + 1) - 1;
                bit2D.update(l, query[i].a, query[i].a, r, i);
                bit.update(query[i].a, 1);
            }
            else {
                curState[ query[i].a ] = '1';
                int l = bit.findPos(bit.get(query[i].a) - 1 ) + 1,
                    r = bit.findPos(bit.get(query[i].a) + 1) - 1;
                bit2D.update(l, query[i].a, query[i].a, r, -i);
                bit.update(query[i].a, -1);
            }
        }
        else {
            cout << bit2D.get(query[i].a, query[i].b) + (bit.get(query[i].b) == bit.get(query[i].a - 1) ? i : 0) << '\n';
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 38776 KB Output is correct
2 Correct 61 ms 38764 KB Output is correct
3 Correct 60 ms 38772 KB Output is correct
4 Correct 61 ms 38776 KB Output is correct
5 Correct 60 ms 38776 KB Output is correct
6 Correct 60 ms 38800 KB Output is correct
7 Correct 60 ms 38776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 78492 KB Output is correct
2 Correct 1229 ms 76320 KB Output is correct
3 Correct 1471 ms 73708 KB Output is correct
4 Correct 2164 ms 99684 KB Output is correct
5 Correct 1892 ms 94632 KB Output is correct
6 Correct 2450 ms 104364 KB Output is correct
7 Correct 305 ms 45940 KB Output is correct
8 Correct 283 ms 47264 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 39220 KB Output is correct
2 Correct 71 ms 39092 KB Output is correct
3 Correct 69 ms 39012 KB Output is correct
4 Correct 60 ms 38776 KB Output is correct
5 Correct 3388 ms 122340 KB Output is correct
6 Correct 2740 ms 114220 KB Output is correct
7 Correct 1866 ms 99492 KB Output is correct
8 Correct 274 ms 47332 KB Output is correct
9 Correct 156 ms 42488 KB Output is correct
10 Correct 168 ms 42744 KB Output is correct
11 Correct 164 ms 43004 KB Output is correct
12 Correct 295 ms 45920 KB Output is correct
13 Correct 279 ms 47332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 39032 KB Output is correct
2 Correct 75 ms 39032 KB Output is correct
3 Correct 80 ms 39032 KB Output is correct
4 Correct 74 ms 39288 KB Output is correct
5 Correct 688 ms 65224 KB Output is correct
6 Correct 1595 ms 89488 KB Output is correct
7 Correct 2408 ms 103528 KB Output is correct
8 Correct 3532 ms 135828 KB Output is correct
9 Correct 1729 ms 99848 KB Output is correct
10 Correct 2045 ms 117988 KB Output is correct
11 Correct 1684 ms 100220 KB Output is correct
12 Correct 2053 ms 117968 KB Output is correct
13 Correct 1710 ms 99808 KB Output is correct
14 Correct 2052 ms 118120 KB Output is correct
15 Correct 306 ms 45924 KB Output is correct
16 Correct 289 ms 47556 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 38776 KB Output is correct
2 Correct 61 ms 38764 KB Output is correct
3 Correct 60 ms 38772 KB Output is correct
4 Correct 61 ms 38776 KB Output is correct
5 Correct 60 ms 38776 KB Output is correct
6 Correct 60 ms 38800 KB Output is correct
7 Correct 60 ms 38776 KB Output is correct
8 Correct 1166 ms 78492 KB Output is correct
9 Correct 1229 ms 76320 KB Output is correct
10 Correct 1471 ms 73708 KB Output is correct
11 Correct 2164 ms 99684 KB Output is correct
12 Correct 1892 ms 94632 KB Output is correct
13 Correct 2450 ms 104364 KB Output is correct
14 Correct 305 ms 45940 KB Output is correct
15 Correct 283 ms 47264 KB Output is correct
16 Correct 74 ms 39220 KB Output is correct
17 Correct 71 ms 39092 KB Output is correct
18 Correct 69 ms 39012 KB Output is correct
19 Correct 60 ms 38776 KB Output is correct
20 Correct 3388 ms 122340 KB Output is correct
21 Correct 2740 ms 114220 KB Output is correct
22 Correct 1866 ms 99492 KB Output is correct
23 Correct 274 ms 47332 KB Output is correct
24 Correct 156 ms 42488 KB Output is correct
25 Correct 168 ms 42744 KB Output is correct
26 Correct 164 ms 43004 KB Output is correct
27 Correct 295 ms 45920 KB Output is correct
28 Correct 279 ms 47332 KB Output is correct
29 Correct 68 ms 39032 KB Output is correct
30 Correct 75 ms 39032 KB Output is correct
31 Correct 80 ms 39032 KB Output is correct
32 Correct 74 ms 39288 KB Output is correct
33 Correct 688 ms 65224 KB Output is correct
34 Correct 1595 ms 89488 KB Output is correct
35 Correct 2408 ms 103528 KB Output is correct
36 Correct 3532 ms 135828 KB Output is correct
37 Correct 1729 ms 99848 KB Output is correct
38 Correct 2045 ms 117988 KB Output is correct
39 Correct 1684 ms 100220 KB Output is correct
40 Correct 2053 ms 117968 KB Output is correct
41 Correct 1710 ms 99808 KB Output is correct
42 Correct 2052 ms 118120 KB Output is correct
43 Correct 306 ms 45924 KB Output is correct
44 Correct 289 ms 47556 KB Output is correct
45 Correct 605 ms 69396 KB Output is correct
46 Correct 769 ms 66596 KB Output is correct
47 Correct 1360 ms 77272 KB Output is correct
48 Correct 2183 ms 104368 KB Output is correct
49 Correct 170 ms 42872 KB Output is correct
50 Correct 171 ms 42848 KB Output is correct
51 Correct 181 ms 43124 KB Output is correct
52 Correct 178 ms 43384 KB Output is correct
53 Correct 180 ms 43504 KB Output is correct
54 Correct 176 ms 43384 KB Output is correct