oj.uz

Submission #258740

# Submission time Handle Problem Language Result Execution time Memory
258740 2020-08-06T13:09:07 Z doowey Street Lamps (APIO19_street_lamps) C++14
20 / 100
 4801 ms 524292 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;

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

int n;
struct ST1D{
    vector<Node> T;
    int cur_id;
    int add_node(){
        T.push_back({0, 0ll, -1, -1});
        cur_id ++ ;
        return cur_id - 1 ;
    }
    void init(){
        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].cur_id == 0)
        seg[node].init();
    seg[node].upd(0, 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].cur_id != 0)
            return seg[node].query(0,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 23 ms 37888 KB Output is correct
2 Correct 22 ms 37888 KB Output is correct
3 Correct 22 ms 38016 KB Output is correct
4 Correct 23 ms 38016 KB Output is correct
5 Correct 22 ms 38016 KB Output is correct
6 Correct 22 ms 37888 KB Output is correct
7 Correct 22 ms 37888 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 42104 KB Output is correct
2 Correct 494 ms 42360 KB Output is correct
3 Correct 1275 ms 53920 KB Output is correct
4 Correct 4801 ms 512320 KB Output is correct
5 Correct 4678 ms 488708 KB Output is correct
6 Runtime error 4510 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39164 KB Output is correct
2 Correct 27 ms 39200 KB Output is correct
3 Correct 26 ms 38912 KB Output is correct
4 Correct 30 ms 38008 KB Output is correct
5 Runtime error 4738 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38528 KB Output is correct
2 Correct 25 ms 38776 KB Output is correct
3 Correct 26 ms 39032 KB Output is correct
4 Correct 28 ms 39040 KB Output is correct
5 Correct 1219 ms 387828 KB Output is correct
6 Correct 3075 ms 469136 KB Output is correct
7 Runtime error 4531 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 37888 KB Output is correct
2 Correct 22 ms 37888 KB Output is correct
3 Correct 22 ms 38016 KB Output is correct
4 Correct 23 ms 38016 KB Output is correct
5 Correct 22 ms 38016 KB Output is correct
6 Correct 22 ms 37888 KB Output is correct
7 Correct 22 ms 37888 KB Output is correct
8 Correct 361 ms 42104 KB Output is correct
9 Correct 494 ms 42360 KB Output is correct
10 Correct 1275 ms 53920 KB Output is correct
11 Correct 4801 ms 512320 KB Output is correct
12 Correct 4678 ms 488708 KB Output is correct
13 Runtime error 4510 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -