oj.uz

Submission #733509

# Submission time Handle Problem Language Result Execution time Memory
733509 2023-05-01T01:07:33 Z Username4132 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 2364 ms 202012 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;


    }
}

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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 86092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 141720 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42524 KB Output is correct
2 Correct 22 ms 42708 KB Output is correct
3 Correct 23 ms 42872 KB Output is correct
4 Correct 25 ms 42896 KB Output is correct
5 Correct 362 ms 66144 KB Output is correct
6 Correct 984 ms 113340 KB Output is correct
7 Correct 1472 ms 152552 KB Output is correct
8 Correct 2243 ms 201948 KB Output is correct
9 Correct 367 ms 89616 KB Output is correct
10 Correct 455 ms 94380 KB Output is correct
11 Correct 431 ms 96660 KB Output is correct
12 Correct 2245 ms 200456 KB Output is correct
13 Correct 2364 ms 202012 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42964 KB Output is correct
2 Runtime error 54 ms 86784 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 86092 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -