oj.uz

Submission #126434

# Submission time Handle Problem Language Result Execution time Memory
126434 2019-07-07T18:13:11 Z keko37 Street Lamps (APIO19_street_lamps) C++14
60 / 100
 5000 ms 203124 KB 
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 300005;

int n, q, ofs = 1;
string s;
map <int, int> mp, lef, rig;
set <int> st;
set <int> :: iterator it;

struct tournament {
    int root = 1, cnt = 1;
    vector <int> t, lef, rig;
    tournament () {
        t.push_back(0);
        lef.push_back(0); rig.push_back(0);
    }
    void novi () {
        cnt++;
        t.push_back(0);
        lef.push_back(0); rig.push_back(0);
    }
    void update (int x, int pos, int lo, int hi, int val) {
        if (lo == hi) {
            t[x-1] += val;
            return;
        }
        int mid = (lo + hi) / 2;
        if (pos <= mid) {
            if (lef[x-1] == 0) {
                novi();
                lef[x-1] = cnt;
            }
            update(lef[x-1], pos, lo, mid, val);
        } else {
            if (rig[x-1] == 0) {
                novi();
                rig[x-1] = cnt;
            }
            update(rig[x-1], pos, mid+1, hi, val);
        }
        t[x-1] = t[lef[x-1]-1] + t[rig[x-1]-1];
    }
    int upit (int x, int from, int to, int lo, int hi) {
        if (x == 0) return 0;
        if (from <= lo && hi <= to) return t[x-1];
        if (to < lo || hi < from) return 0;
        return upit(lef[x-1], from, to, lo, (lo + hi)/2) + upit(rig[x-1], from, to, (lo + hi)/2+1, hi);
    }
} fen[MAXN];

void ubaci (int x, int y, int val) {
    for (; x < MAXN; x += x&-x) {
        fen[x].update(1, y, 0, ofs-1, val);
    }
}

int upit (int x, int y) {
    int res = 0;
    for (; x > 0; x -= x&-x) {
        res += fen[x].upit(1, y, ofs-1, 0, ofs-1);
    }
    return res;
}

void dodaj (int a, int b, int t) {
    st.insert(a);
    mp[a] = t;
    rig[a] = b; lef[b] = a;
}

void brisi (int a, int b, int t) {
    ubaci(a, b, t - mp[a]);
    st.erase(a);
    mp.erase(a);
    rig.erase(a); lef.erase(b);
}

void precompute () {
    int lim = -1;
    for (int i=1; i<=n; i++) {
        if (s[i] == '1' && (i == 1 || s[i-1] == '0')) lim = i;
        if (s[i] == '1' && (i == n || s[i+1] == '0')) {
            dodaj(lim, i, 0);
        }
    }
}

void ispis () {
    cout << "ispis" << endl;
    for (auto x : st) {
        cout << "bla " << x << " " << rig[x] << "  " << mp[x] << endl;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> s;
    s = '.' + s;
    while (ofs < n+1) ofs *= 2;
    precompute();
    for (int i=1; i<=q; i++) {
        string t;
        cin >> t;
        if (t == "query") {
            int a, b;
            cin >> a >> b; b--;
            int res = upit(a, b);
            it = st.upper_bound(a);
            if (it != st.begin()) {
                it--;
                if (b <= rig[*it]) {
                    res += i - mp[*it];
                }
            }
            cout << res << '\n';
        } else {
            int x;
            cin >> x;
            if (s[x] == '0') {
                s[x] = '1';
                int ll = x, rr = x;
                it = st.upper_bound(x);
                if (it != st.end() && *it == x+1) {
                    rr = rig[*it];
                    brisi(*it, rig[*it], i);
                }
                it = st.upper_bound(x);
                if (it != st.begin()) {
                    it--;
                    if (rig[*it] == x-1) {
                        ll = *it;
                        brisi(*it, rig[*it], i);
                    }
                }
                dodaj(ll, rr, i);
            } else {
                s[x] = '0';
                it = st.upper_bound(x); it--;
                int ll = *it;
                int rr = rig[*it];
                brisi(ll, rr, i);
                if (ll <= x-1) dodaj(ll, x-1, i);
                if (x+1 <= rr) dodaj(x+1, rr, i);
            }
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 52044 KB Output is correct
2 Correct 84 ms 52088 KB Output is correct
3 Correct 84 ms 52088 KB Output is correct
4 Correct 85 ms 52088 KB Output is correct
5 Correct 85 ms 52088 KB Output is correct
6 Correct 84 ms 51964 KB Output is correct
7 Correct 84 ms 51956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 56244 KB Output is correct
2 Correct 720 ms 56836 KB Output is correct
3 Correct 1286 ms 61248 KB Output is correct
4 Correct 3358 ms 171468 KB Output is correct
5 Correct 3291 ms 177572 KB Output is correct
6 Correct 3466 ms 176904 KB Output is correct
7 Correct 330 ms 59012 KB Output is correct
8 Correct 352 ms 60456 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 52564 KB Output is correct
2 Correct 98 ms 52560 KB Output is correct
3 Correct 95 ms 52472 KB Output is correct
4 Correct 99 ms 51964 KB Output is correct
5 Correct 4517 ms 203124 KB Output is correct
6 Correct 4399 ms 197460 KB Output is correct
7 Correct 2988 ms 176492 KB Output is correct
8 Correct 346 ms 60464 KB Output is correct
9 Correct 193 ms 55800 KB Output is correct
10 Correct 202 ms 56056 KB Output is correct
11 Correct 206 ms 56312 KB Output is correct
12 Correct 371 ms 59000 KB Output is correct
13 Correct 363 ms 60352 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 52220 KB Output is correct
2 Correct 95 ms 52316 KB Output is correct
3 Correct 95 ms 52472 KB Output is correct
4 Correct 97 ms 52748 KB Output is correct
5 Correct 1014 ms 79312 KB Output is correct
6 Correct 2113 ms 143948 KB Output is correct
7 Correct 3276 ms 176616 KB Output is correct
8 Execution timed out 5096 ms 193144 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 52044 KB Output is correct
2 Correct 84 ms 52088 KB Output is correct
3 Correct 84 ms 52088 KB Output is correct
4 Correct 85 ms 52088 KB Output is correct
5 Correct 85 ms 52088 KB Output is correct
6 Correct 84 ms 51964 KB Output is correct
7 Correct 84 ms 51956 KB Output is correct
8 Correct 559 ms 56244 KB Output is correct
9 Correct 720 ms 56836 KB Output is correct
10 Correct 1286 ms 61248 KB Output is correct
11 Correct 3358 ms 171468 KB Output is correct
12 Correct 3291 ms 177572 KB Output is correct
13 Correct 3466 ms 176904 KB Output is correct
14 Correct 330 ms 59012 KB Output is correct
15 Correct 352 ms 60456 KB Output is correct
16 Correct 98 ms 52564 KB Output is correct
17 Correct 98 ms 52560 KB Output is correct
18 Correct 95 ms 52472 KB Output is correct
19 Correct 99 ms 51964 KB Output is correct
20 Correct 4517 ms 203124 KB Output is correct
21 Correct 4399 ms 197460 KB Output is correct
22 Correct 2988 ms 176492 KB Output is correct
23 Correct 346 ms 60464 KB Output is correct
24 Correct 193 ms 55800 KB Output is correct
25 Correct 202 ms 56056 KB Output is correct
26 Correct 206 ms 56312 KB Output is correct
27 Correct 371 ms 59000 KB Output is correct
28 Correct 363 ms 60352 KB Output is correct
29 Correct 93 ms 52220 KB Output is correct
30 Correct 95 ms 52316 KB Output is correct
31 Correct 95 ms 52472 KB Output is correct
32 Correct 97 ms 52748 KB Output is correct
33 Correct 1014 ms 79312 KB Output is correct
34 Correct 2113 ms 143948 KB Output is correct
35 Correct 3276 ms 176616 KB Output is correct
36 Execution timed out 5096 ms 193144 KB Time limit exceeded
37 Halted 0 ms 0 KB -