oj.uz

Submission #258742

# Submission time Handle Problem Language Result Execution time Memory
258742 2020-08-06T13:14:24 Z doowey Street Lamps (APIO19_street_lamps) C++14
100 / 100
 3417 ms 286548 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
const int M = (int)3e7;

struct Node{
    int f1;
    int f2;
    int li;
    int ri;
};

Node T[M];

int mx_id = 0;

int n;
struct ST1D{
    int root=-1;
    int add_node(){
        T[mx_id++]={0, 0ll, -1, -1};
        return mx_id - 1 ;
    }
    void init(){
        root=add_node();
    }
    void upd(int node, int cl, int cr, int pos, int ti, int vi){
        if(cl == cr){
            T[node].f1 += vi;
            T[node].f2 += -ti * 1ll * vi;
            return ;
        }
        int mid = (cl + cr) / 2;
        if(mid >= pos){
            if(T[node].li == -1){
                int nx = add_node();
                T[node].li = nx;
            }
            upd(T[node].li, cl, mid, pos, ti, vi);
        }
        else{
            if(T[node].ri == -1){
                int nx = add_node();
                T[node].ri = nx;
            }
            upd(T[node].ri, mid + 1, cr, pos, ti, vi);
        }
        T[node].f1 = T[node].f2 = 0;
        if(T[node].li != -1) {
            T[node].f1 += T[T[node].li].f1;
            T[node].f2 += T[T[node].li].f2;
        }
        if(T[node].ri != -1){
            T[node].f1 += T[T[node].ri].f1;
            T[node].f2 += T[T[node].ri].f2;
        }
    }
    ll query(int node, int cl, int cr, int tl, int tr, int tt){
        if(node == -1 || cr < tl || cl > tr) return 0;
        if(cl >= tl && cr <= tr){
            return tt * 1ll * T[node].f1 + T[node].f2;
        }
        int mid = (cl + cr) / 2;
        return query(T[node].li, cl, mid, tl, tr, tt) + query(T[node].ri, mid + 1, cr, tl, tr, tt);
    }
};

ST1D seg[N * 4 + 512];

void upd_it(int node, int cl, int cr, int pos, int ti, int vi, int ri){
    if(seg[node].root==-1)
        seg[node].init();
    seg[node].upd(seg[node].root, 1, n, ri, ti, vi);
    if(cl == cr)
        return;
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        upd_it(node * 2, cl, mid, pos, ti, vi, ri);
    else
        upd_it(node * 2 + 1, mid + 1, cr, pos, ti, vi, ri);
}

ll ask(int node, int cl, int cr, int tl, int tr, int R, int tt){
    if(cr < tl)
        return 0;
    if(cl > tr)
        return 0;
    if(cl >= tl && cr <= tr){
        if(seg[node].root != -1)
            return seg[node].query(seg[node].root,1,n,R,n,tt);
        else
            return 0;
    }
    int mid = (cl + cr) / 2;
    return ask(node * 2, cl, mid, tl, tr, R, tt) + ask(node * 2 + 1, mid + 1, cr, tl, tr, R, tt);
}

set<pii> segs;
int vl[N];
int vv[N];

void toggle(int id, int ti){
    if(vl[id] == 0){
        auto it = segs.lower_bound(mp(id + 1, -1));
        int nl, nr;
        nl = nr = id;
        if(it != segs.end()){
            if(it->fi == id + 1){
                upd_it(1, 1, n, it->fi, ti, -1, it->se);
                nr = it->se;
                it = segs.erase(it);
            }
        }
        if(it != segs.begin()){
            it--;
            if(it->se == id - 1){
                upd_it(1, 1, n, it->fi, ti, -1, it->se);
                nl = it->fi;
                segs.erase(it);
            }
        }
        segs.insert(mp(nl, nr));
        upd_it(1, 1, n, nl, ti, +1, nr);
        vl[id] ^= 1;
    }
    else{
        auto it = segs.lower_bound(mp(id + 1, -1));
        it--;
        int cl = it->fi;
        int cr = it->se;
        segs.erase(it);
        upd_it(1, 1, n, cl, ti, -1, cr);
        if(cl < id){
            segs.insert(mp(cl, id - 1));
            upd_it(1, 1, n, cl, ti, +1, id-1);
        }
        if(id < cr){
            segs.insert(mp(id + 1, cr));
            upd_it(1, 1, n, id + 1, ti, +1, cr);
        }
        vl[id] ^= 1;
    }
}


int main(){
    fastIO;
    int q;
    cin >> n >> q;
    char f;
    int lv = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> f;
        vl[i]=f-'0';
        if(vl[i] == 1){
            if(lv == 0) lv = i;
        }
        if(lv > 0){
            if(vl[i] == 0){
                segs.insert(mp(lv, i-1));
                upd_it(1, 1, n, lv, 0, +1, i-1);
                lv = 0;
            }
            else if(i == n){
                segs.insert(mp(lv, n));
                upd_it(1, 1, n, lv, 0, +1, n);
                lv = 0;
            }
        }
    }

    string typ;
    int li, ri;
    for(int tv = 1; tv <= q; tv ++ ){
        cin >> typ;
        if(typ == "toggle"){
            cin >> li;
            toggle(li,tv);
        }
        else{
            cin >> li >> ri;
            ri--;
            cout << ask(1, 1, n, 1, li, ri, tv) << "\n";
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 1528 KB Output is correct
2 Correct 399 ms 1784 KB Output is correct
3 Correct 768 ms 7192 KB Output is correct
4 Correct 2264 ms 236560 KB Output is correct
5 Correct 2324 ms 219832 KB Output is correct
6 Correct 2523 ms 252092 KB Output is correct
7 Correct 188 ms 8056 KB Output is correct
8 Correct 194 ms 9464 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3351 ms 286548 KB Output is correct
6 Correct 2890 ms 274876 KB Output is correct
7 Correct 2044 ms 224456 KB Output is correct
8 Correct 204 ms 9740 KB Output is correct
9 Correct 92 ms 4088 KB Output is correct
10 Correct 106 ms 4536 KB Output is correct
11 Correct 106 ms 4728 KB Output is correct
12 Correct 182 ms 8048 KB Output is correct
13 Correct 203 ms 9568 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 600 ms 166212 KB Output is correct
6 Correct 1414 ms 212856 KB Output is correct
7 Correct 2310 ms 251288 KB Output is correct
8 Correct 3417 ms 283048 KB Output is correct
9 Correct 470 ms 4472 KB Output is correct
10 Correct 366 ms 3452 KB Output is correct
11 Correct 490 ms 4596 KB Output is correct
12 Correct 382 ms 3448 KB Output is correct
13 Correct 496 ms 4472 KB Output is correct
14 Correct 379 ms 3580 KB Output is correct
15 Correct 180 ms 8056 KB Output is correct
16 Correct 224 ms 9564 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 290 ms 1528 KB Output is correct
9 Correct 399 ms 1784 KB Output is correct
10 Correct 768 ms 7192 KB Output is correct
11 Correct 2264 ms 236560 KB Output is correct
12 Correct 2324 ms 219832 KB Output is correct
13 Correct 2523 ms 252092 KB Output is correct
14 Correct 188 ms 8056 KB Output is correct
15 Correct 194 ms 9464 KB Output is correct
16 Correct 4 ms 896 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 768 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 3351 ms 286548 KB Output is correct
21 Correct 2890 ms 274876 KB Output is correct
22 Correct 2044 ms 224456 KB Output is correct
23 Correct 204 ms 9740 KB Output is correct
24 Correct 92 ms 4088 KB Output is correct
25 Correct 106 ms 4536 KB Output is correct
26 Correct 106 ms 4728 KB Output is correct
27 Correct 182 ms 8048 KB Output is correct
28 Correct 203 ms 9568 KB Output is correct
29 Correct 1 ms 640 KB Output is correct
30 Correct 2 ms 768 KB Output is correct
31 Correct 3 ms 768 KB Output is correct
32 Correct 4 ms 896 KB Output is correct
33 Correct 600 ms 166212 KB Output is correct
34 Correct 1414 ms 212856 KB Output is correct
35 Correct 2310 ms 251288 KB Output is correct
36 Correct 3417 ms 283048 KB Output is correct
37 Correct 470 ms 4472 KB Output is correct
38 Correct 366 ms 3452 KB Output is correct
39 Correct 490 ms 4596 KB Output is correct
40 Correct 382 ms 3448 KB Output is correct
41 Correct 496 ms 4472 KB Output is correct
42 Correct 379 ms 3580 KB Output is correct
43 Correct 180 ms 8056 KB Output is correct
44 Correct 224 ms 9564 KB Output is correct
45 Correct 93 ms 2808 KB Output is correct
46 Correct 201 ms 2808 KB Output is correct
47 Correct 1028 ms 88972 KB Output is correct
48 Correct 2013 ms 241528 KB Output is correct
49 Correct 113 ms 4472 KB Output is correct
50 Correct 111 ms 4508 KB Output is correct
51 Correct 111 ms 4700 KB Output is correct
52 Correct 129 ms 4984 KB Output is correct
53 Correct 121 ms 4984 KB Output is correct
54 Correct 123 ms 4988 KB Output is correct