oj.uz

Submission #733515

# Submission time Handle Problem Language Result Execution time Memory
733515 2023-05-01T01:23:36 Z Username4132 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2467 ms 205504 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=300010;
int n, m;
string str;


ll sum(vector<ll>& bit, int r){
    ll ret=0;
    for(; r>=0; r=(r&(r+1))-1) ret+=bit[r];
    return ret;
}

void add(vector<ll>& bit, int r, int delta){
    for(; r<(int)bit.size(); r=r|(r+1)) bit[r]+=delta;
}

void add(vector<ll>& bit, int l, int r, int delta){
    add(bit, l, delta);
    add(bit, r, -delta);
}

struct fen{
    vector<int> nd;
    vector<ll> e, t;
    void su(bool mode, int bl, int br, int delta){
        int l = lower_bound(nd.begin(), nd.end(), bl) - nd.begin();
        int r = lower_bound(nd.begin(), nd.end(), br) - nd.begin();
        if(mode) add(e, l, r, delta);
        else add(t, l, r, delta);
    }
};

set<int> tur;
bool sw[MAXN];
fen tr[2*MAXN];

fen combine(fen a, fen b){
    fen ret;
    int sz=a.nd.size()+b.nd.size();
    ret.nd.resize(sz), ret.e.resize(sz), ret.t.resize(sz);
    merge(a.nd.begin(), a.nd.end(), b.nd.begin(), b.nd.end(), ret.nd.begin());
    return ret;
}

void update(int l, int r, bool mode, int bl, int br, int tm){
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1) tr[l++].su(mode, bl, br, tm);
        if(r&1) tr[--r].su(mode, bl, br, tm);
    }
}

void toggle(int ind, int tm){
    if(sw[ind]){
        sw[ind]=false;
        auto itr=tur.find(ind), nx=next(itr);
        int start = itr==tur.begin()? 0 : ((*prev(itr))+1);
        int en = ind+1;
        int bnd = nx==tur.end()? n : ((*nx)+1);
        tur.erase(itr);
        update(start, en, 0, en, bnd, tm);

    }
    else{
        sw[ind]=true;
        auto itr = tur.insert(ind).F, nx=next(itr);
        int start = itr==tur.begin()? 0 : ((*prev(itr))+1);
        int en = ind+1;
        int bnd = nx==tur.end()? n : ((*nx)+1);
        update(start, en, 1, en, bnd, tm);
    }
}

ll query(int l, int r, int tm){
    ll ret=0;
    int l0=l;
    l+=n;
    while(l>0){
        auto itr=lower_bound(tr[l].nd.begin(), tr[l].nd.end(), r);
        //assert(itr!=tr[l].nd.end() && *itr==r);
        int pos=itr-tr[l].nd.begin();
        ret+=sum(tr[l].e, pos);
        ret-=sum(tr[l].t, pos);
        l>>=1;
    }

    auto itr=tur.lower_bound(l0);
    if(itr==tur.end() || *itr>=r){
        ret+=tm;
    }
    return ret;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> str;
    ++n;

    vector<pii> qrs(m);

    forn(i, m){
        string type;
        cin >> type;
        if(type[0]=='q'){
            int a, b; cin >> a >> b; --a, --b;
            qrs[i]={a, b};
            tr[n+a].nd.PB(b);
        }
        else{
            int a; cin >> a; --a;
            qrs[i]={a, -1};
        }
    }

    forn(i, n){
        sort(tr[n+i].nd.begin(), tr[n+i].nd.end());
        tr[n+i].e.resize(tr[n+i].nd.size());
        tr[n+i].t.resize(tr[n+i].nd.size());
    }

    for(int i=n-1; i>0; --i) tr[i]=combine(tr[i<<1], tr[i<<1|1]);

    forn(i, n-1) tur.insert(i), sw[i]=true;
    forn(i, n-1) if(str[i]=='1') toggle(i, -1);
    forn(i, m){
        if(qrs[i].S==-1){
            toggle(qrs[i].F, i);
        }
        else{
            ll ans = query(qrs[i].F, qrs[i].S, i);
            cout << ans << '\n';
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42492 KB Output is correct
2 Correct 22 ms 42532 KB Output is correct
3 Correct 24 ms 42504 KB Output is correct
4 Correct 23 ms 42552 KB Output is correct
5 Correct 20 ms 42524 KB Output is correct
6 Correct 22 ms 42588 KB Output is correct
7 Correct 21 ms 42516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 71940 KB Output is correct
2 Correct 443 ms 79704 KB Output is correct
3 Correct 736 ms 92812 KB Output is correct
4 Correct 1328 ms 142540 KB Output is correct
5 Correct 1575 ms 155728 KB Output is correct
6 Correct 1217 ms 129300 KB Output is correct
7 Correct 2321 ms 204216 KB Output is correct
8 Correct 2219 ms 205504 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42580 KB Output is correct
2 Correct 24 ms 42708 KB Output is correct
3 Correct 27 ms 42800 KB Output is correct
4 Correct 24 ms 42876 KB Output is correct
5 Correct 361 ms 62244 KB Output is correct
6 Correct 922 ms 108704 KB Output is correct
7 Correct 1514 ms 147244 KB Output is correct
8 Correct 2257 ms 196208 KB Output is correct
9 Correct 367 ms 86852 KB Output is correct
10 Correct 417 ms 91324 KB Output is correct
11 Correct 421 ms 93560 KB Output is correct
12 Correct 2303 ms 194680 KB Output is correct
13 Correct 2210 ms 196136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42880 KB Output is correct
2 Correct 27 ms 42880 KB Output is correct
3 Correct 24 ms 42800 KB Output is correct
4 Correct 23 ms 42668 KB Output is correct
5 Correct 2415 ms 199412 KB Output is correct
6 Correct 1682 ms 164604 KB Output is correct
7 Correct 1090 ms 126844 KB Output is correct
8 Correct 419 ms 66640 KB Output is correct
9 Correct 291 ms 66196 KB Output is correct
10 Correct 129 ms 48848 KB Output is correct
11 Correct 334 ms 66112 KB Output is correct
12 Correct 126 ms 48852 KB Output is correct
13 Correct 294 ms 66196 KB Output is correct
14 Correct 141 ms 48764 KB Output is correct
15 Correct 2467 ms 200700 KB Output is correct
16 Correct 2255 ms 201908 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42492 KB Output is correct
2 Correct 22 ms 42532 KB Output is correct
3 Correct 24 ms 42504 KB Output is correct
4 Correct 23 ms 42552 KB Output is correct
5 Correct 20 ms 42524 KB Output is correct
6 Correct 22 ms 42588 KB Output is correct
7 Correct 21 ms 42516 KB Output is correct
8 Correct 284 ms 71940 KB Output is correct
9 Correct 443 ms 79704 KB Output is correct
10 Correct 736 ms 92812 KB Output is correct
11 Correct 1328 ms 142540 KB Output is correct
12 Correct 1575 ms 155728 KB Output is correct
13 Correct 1217 ms 129300 KB Output is correct
14 Correct 2321 ms 204216 KB Output is correct
15 Correct 2219 ms 205504 KB Output is correct
16 Correct 23 ms 42580 KB Output is correct
17 Correct 24 ms 42708 KB Output is correct
18 Correct 27 ms 42800 KB Output is correct
19 Correct 24 ms 42876 KB Output is correct
20 Correct 361 ms 62244 KB Output is correct
21 Correct 922 ms 108704 KB Output is correct
22 Correct 1514 ms 147244 KB Output is correct
23 Correct 2257 ms 196208 KB Output is correct
24 Correct 367 ms 86852 KB Output is correct
25 Correct 417 ms 91324 KB Output is correct
26 Correct 421 ms 93560 KB Output is correct
27 Correct 2303 ms 194680 KB Output is correct
28 Correct 2210 ms 196136 KB Output is correct
29 Correct 25 ms 42880 KB Output is correct
30 Correct 27 ms 42880 KB Output is correct
31 Correct 24 ms 42800 KB Output is correct
32 Correct 23 ms 42668 KB Output is correct
33 Correct 2415 ms 199412 KB Output is correct
34 Correct 1682 ms 164604 KB Output is correct
35 Correct 1090 ms 126844 KB Output is correct
36 Correct 419 ms 66640 KB Output is correct
37 Correct 291 ms 66196 KB Output is correct
38 Correct 129 ms 48848 KB Output is correct
39 Correct 334 ms 66112 KB Output is correct
40 Correct 126 ms 48852 KB Output is correct
41 Correct 294 ms 66196 KB Output is correct
42 Correct 141 ms 48764 KB Output is correct
43 Correct 2467 ms 200700 KB Output is correct
44 Correct 2255 ms 201908 KB Output is correct
45 Correct 120 ms 57164 KB Output is correct
46 Correct 240 ms 63916 KB Output is correct
47 Correct 746 ms 94180 KB Output is correct
48 Correct 1382 ms 139728 KB Output is correct
49 Correct 562 ms 100872 KB Output is correct
50 Correct 503 ms 99764 KB Output is correct
51 Correct 521 ms 103832 KB Output is correct
52 Correct 512 ms 116472 KB Output is correct
53 Correct 590 ms 116408 KB Output is correct
54 Correct 561 ms 116448 KB Output is correct