oj.uz

Submission #603883

# Submission time Handle Problem Language Result Execution time Memory
603883 2022-07-24T12:59:38 Z OttoTheDino Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2701 ms 114756 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define pb                          push_back
#define fi                          first
#define se                          second
#define len(a)                      (int)a.size()
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int mx = 3e5;
int ans[mx+1], ft[mx+1];
vector<vi> g;

void upd (int x, int id) {
    for (;id<=mx;id+=id&(-id)) ft[id] += x;
}
int qry (int id) {
    int res = 0;
    for (;id;id-=id&(-id)) res += ft[id];
    return res;
}

void cdq (int l, int r) {
    if (l==r) return;
    int mid = (l+r)/2;
    cdq (l, mid);
    cdq (mid+1, r);
    vii undo;
    vector<vi> nxt;
    int a = l, b = mid+1, k = l;
    while (k<=r) {
        if (a>mid || (b<=r && g[b]<g[a])) nxt.pb(g[b++]);
        else nxt.pb(g[a++]);
        ++k;
    }
    rep (i,l,r) g[i] = nxt[i-l];
    rep (i,l,r) {
        int y = g[i][1], id = g[i][2], delt = g[i][3], t = g[i][4];
        if (t>mid) ans[id] += qry(y);
        else {
            upd(delt,y);
            undo.pb({delt,y});
        }
    }
    for (ii el : undo) upd(-el.fi, el.se);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    bool b[n+1]; 
    string s; cin >> s;
    set<int> st;
    st.insert(0);
    st.insert(n+1);
    rep (i,1,n) {
        b[i] = s[i-1]-'0';
        if (!b[i]) st.insert(i);
    }
    vi get;
    rep (i,1,q) {
        string tp; cin >> tp;
        int t = len(g);
        if (tp[0]=='t') {
            int u; cin >> u;
            int prv = *--st.lower_bound(u)+1, nxt = *st.upper_bound(u)-1, c = 2*b[u]-1;
            g.pb({prv,mx+1-nxt,0,c*i,t++}); 
            if (u+1<=mx) g.pb({u+1,mx+1-nxt,0,-c*i,t++});
            if (u-1>0) g.pb({prv,mx+1-(u-1),0,-c*i,t++});
            if (b[u]) st.insert(u);
            else st.erase(u);
            b[u] ^= 1;
        }
        else {
            int x, y; cin >> x >> y;
            --y;
            get.pb(i);
            if (*st.lower_bound(x)>y) ans[i] += i;
            g.pb({x,mx+1-y,i,0,t++});
        }
    }
    cdq(0,len(g)-1);
    for (int el : get) cout << ans[el] << "\n";

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1227 ms 77720 KB Output is correct
2 Correct 1210 ms 77724 KB Output is correct
3 Correct 1327 ms 77892 KB Output is correct
4 Correct 1556 ms 86672 KB Output is correct
5 Correct 1559 ms 76692 KB Output is correct
6 Correct 1735 ms 90596 KB Output is correct
7 Correct 921 ms 56268 KB Output is correct
8 Correct 749 ms 42348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 4 ms 560 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2701 ms 113424 KB Output is correct
6 Correct 2225 ms 93152 KB Output is correct
7 Correct 1464 ms 76856 KB Output is correct
8 Correct 737 ms 42328 KB Output is correct
9 Correct 421 ms 30712 KB Output is correct
10 Correct 478 ms 37660 KB Output is correct
11 Correct 463 ms 37412 KB Output is correct
12 Correct 941 ms 56468 KB Output is correct
13 Correct 767 ms 42352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 905 ms 49840 KB Output is correct
6 Correct 1270 ms 67528 KB Output is correct
7 Correct 1647 ms 90596 KB Output is correct
8 Correct 2328 ms 114756 KB Output is correct
9 Correct 1608 ms 89004 KB Output is correct
10 Correct 1965 ms 105200 KB Output is correct
11 Correct 1559 ms 89028 KB Output is correct
12 Correct 1930 ms 105120 KB Output is correct
13 Correct 1779 ms 89020 KB Output is correct
14 Correct 1882 ms 105184 KB Output is correct
15 Correct 995 ms 56340 KB Output is correct
16 Correct 775 ms 42396 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1227 ms 77720 KB Output is correct
9 Correct 1210 ms 77724 KB Output is correct
10 Correct 1327 ms 77892 KB Output is correct
11 Correct 1556 ms 86672 KB Output is correct
12 Correct 1559 ms 76692 KB Output is correct
13 Correct 1735 ms 90596 KB Output is correct
14 Correct 921 ms 56268 KB Output is correct
15 Correct 749 ms 42348 KB Output is correct
16 Correct 5 ms 724 KB Output is correct
17 Correct 4 ms 560 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2701 ms 113424 KB Output is correct
21 Correct 2225 ms 93152 KB Output is correct
22 Correct 1464 ms 76856 KB Output is correct
23 Correct 737 ms 42328 KB Output is correct
24 Correct 421 ms 30712 KB Output is correct
25 Correct 478 ms 37660 KB Output is correct
26 Correct 463 ms 37412 KB Output is correct
27 Correct 941 ms 56468 KB Output is correct
28 Correct 767 ms 42352 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 5 ms 596 KB Output is correct
32 Correct 5 ms 640 KB Output is correct
33 Correct 905 ms 49840 KB Output is correct
34 Correct 1270 ms 67528 KB Output is correct
35 Correct 1647 ms 90596 KB Output is correct
36 Correct 2328 ms 114756 KB Output is correct
37 Correct 1608 ms 89004 KB Output is correct
38 Correct 1965 ms 105200 KB Output is correct
39 Correct 1559 ms 89028 KB Output is correct
40 Correct 1930 ms 105120 KB Output is correct
41 Correct 1779 ms 89020 KB Output is correct
42 Correct 1882 ms 105184 KB Output is correct
43 Correct 995 ms 56340 KB Output is correct
44 Correct 775 ms 42396 KB Output is correct
45 Correct 707 ms 47872 KB Output is correct
46 Correct 800 ms 48792 KB Output is correct
47 Correct 964 ms 51892 KB Output is correct
48 Correct 1573 ms 86720 KB Output is correct
49 Correct 559 ms 40524 KB Output is correct
50 Correct 561 ms 40520 KB Output is correct
51 Correct 584 ms 40552 KB Output is correct
52 Correct 542 ms 40452 KB Output is correct
53 Correct 552 ms 40436 KB Output is correct
54 Correct 593 ms 40472 KB Output is correct