oj.uz

Submission #124665

# Submission time Handle Problem Language Result Execution time Memory
124665 2019-07-03T16:55:29 Z EntityIT Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 269612 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[2];

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

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

    bit2D[0].init();
    bit2D[1].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[0].add(i + 1, i + 1);
            bit2D[0].add(j, j);
            bit2D[0].add(i + 1, j);
            bit2D[0].add(j, i + 1);
            bit2D[1].add(i + 1, i + 1);
            bit2D[1].add(j, j);
            bit2D[1].add(i + 1, j);
            bit2D[1].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[0].add(l, query[i].a);
            bit2D[0].add(query[i].a + 1, r + 1);
            bit2D[0].add(l, r + 1);
            bit2D[0].add(query[i].a + 1, query[i].a);
            bit2D[1].add(l, query[i].a);
            bit2D[1].add(query[i].a + 1, r + 1);
            bit2D[1].add(l, r + 1);
            bit2D[1].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[0].add(l, query[i].a);
            bit2D[0].add(query[i].a + 1, r + 1);
            bit2D[0].add(l, r + 1);
            bit2D[0].add(query[i].a + 1, query[i].a);
            bit2D[1].add(l, query[i].a);
            bit2D[1].add(query[i].a + 1, r + 1);
            bit2D[1].add(l, r + 1);
            bit2D[1].add(query[i].a + 1, query[i].a);
            bit.update(query[i].a, -1);
        }
    }

    bit.init();
    bit2D[0].interPhase();
    bit2D[1].interPhase();

    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[1].update(i + 1, i + 1, j - 1, j - 1, 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[0].update(l, query[i].a, query[i].a, r, i);
                bit2D[1].update(l, query[i].a, query[i].a, r, -1);
                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[0].update(l, query[i].a, query[i].a, r, -i);
                bit2D[1].update(l, query[i].a, query[i].a, r, 1);
                bit.update(query[i].a, -1);
            }
        }
        else {
            cout << bit2D[0].get(query[i].a, query[i].b) + (bit2D[1].get(query[i].a, query[i].b) ? i : 0) << '\n';
        }
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 71672 KB Output is correct
2 Correct 116 ms 71672 KB Output is correct
3 Correct 117 ms 71672 KB Output is correct
4 Correct 118 ms 71744 KB Output is correct
5 Correct 119 ms 71900 KB Output is correct
6 Correct 117 ms 71716 KB Output is correct
7 Correct 118 ms 71672 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2157 ms 150892 KB Output is correct
2 Correct 2300 ms 146080 KB Output is correct
3 Correct 2800 ms 141208 KB Output is correct
4 Correct 4540 ms 192528 KB Output is correct
5 Correct 4080 ms 181912 KB Output is correct
6 Execution timed out 5019 ms 201656 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 72444 KB Output is correct
2 Correct 143 ms 72440 KB Output is correct
3 Correct 137 ms 72232 KB Output is correct
4 Correct 116 ms 71672 KB Output is correct
5 Execution timed out 5022 ms 238772 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 71928 KB Output is correct
2 Correct 134 ms 72156 KB Output is correct
3 Correct 151 ms 72312 KB Output is correct
4 Correct 143 ms 72668 KB Output is correct
5 Correct 1494 ms 123956 KB Output is correct
6 Correct 3310 ms 171884 KB Output is correct
7 Correct 4997 ms 200688 KB Output is correct
8 Execution timed out 5122 ms 269612 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 71672 KB Output is correct
2 Correct 116 ms 71672 KB Output is correct
3 Correct 117 ms 71672 KB Output is correct
4 Correct 118 ms 71744 KB Output is correct
5 Correct 119 ms 71900 KB Output is correct
6 Correct 117 ms 71716 KB Output is correct
7 Correct 118 ms 71672 KB Output is correct
8 Correct 2157 ms 150892 KB Output is correct
9 Correct 2300 ms 146080 KB Output is correct
10 Correct 2800 ms 141208 KB Output is correct
11 Correct 4540 ms 192528 KB Output is correct
12 Correct 4080 ms 181912 KB Output is correct
13 Execution timed out 5019 ms 201656 KB Time limit exceeded
14 Halted 0 ms 0 KB -