oj.uz

Submission #124663

# Submission time Handle Problem Language Result Execution time Memory
124663 2019-07-03T16:52:45 Z EntityIT Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 368744 KB 
/*
check long long - int
check N
*/
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long

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<int> 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;
        }
    }
    int get (int x, int y) {
        int 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 121 ms 77304 KB Output is correct
2 Correct 124 ms 77304 KB Output is correct
3 Correct 122 ms 77432 KB Output is correct
4 Correct 132 ms 77352 KB Output is correct
5 Correct 132 ms 77304 KB Output is correct
6 Correct 120 ms 77308 KB Output is correct
7 Correct 120 ms 77304 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2335 ms 236104 KB Output is correct
2 Correct 2498 ms 226984 KB Output is correct
3 Correct 3026 ms 216072 KB Output is correct
4 Correct 4894 ms 290888 KB Output is correct
5 Correct 4414 ms 271224 KB Output is correct
6 Execution timed out 5035 ms 307564 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 78652 KB Output is correct
2 Correct 153 ms 78456 KB Output is correct
3 Correct 142 ms 78328 KB Output is correct
4 Correct 122 ms 77316 KB Output is correct
5 Execution timed out 5071 ms 368744 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 77784 KB Output is correct
2 Correct 141 ms 78172 KB Output is correct
3 Correct 145 ms 78456 KB Output is correct
4 Correct 152 ms 78992 KB Output is correct
5 Correct 1706 ms 170448 KB Output is correct
6 Correct 3491 ms 255508 KB Output is correct
7 Execution timed out 5047 ms 306552 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 77304 KB Output is correct
2 Correct 124 ms 77304 KB Output is correct
3 Correct 122 ms 77432 KB Output is correct
4 Correct 132 ms 77352 KB Output is correct
5 Correct 132 ms 77304 KB Output is correct
6 Correct 120 ms 77308 KB Output is correct
7 Correct 120 ms 77304 KB Output is correct
8 Correct 2335 ms 236104 KB Output is correct
9 Correct 2498 ms 226984 KB Output is correct
10 Correct 3026 ms 216072 KB Output is correct
11 Correct 4894 ms 290888 KB Output is correct
12 Correct 4414 ms 271224 KB Output is correct
13 Execution timed out 5035 ms 307564 KB Time limit exceeded
14 Halted 0 ms 0 KB -