oj.uz

Submission #733512

# Submission time Handle Problem Language Result Execution time Memory
733512 2023-05-01T01:16:48 Z Username4132 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 2291 ms 196240 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;
        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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 42580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 71852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42580 KB Output is correct
2 Correct 23 ms 42792 KB Output is correct
3 Correct 25 ms 42800 KB Output is correct
4 Correct 23 ms 42964 KB Output is correct
5 Correct 370 ms 62396 KB Output is correct
6 Correct 913 ms 108600 KB Output is correct
7 Correct 1437 ms 147100 KB Output is correct
8 Correct 2153 ms 196240 KB Output is correct
9 Correct 382 ms 86872 KB Output is correct
10 Correct 442 ms 91280 KB Output is correct
11 Correct 474 ms 93588 KB Output is correct
12 Correct 2291 ms 194644 KB Output is correct
13 Correct 2195 ms 196128 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43040 KB Output is correct
2 Incorrect 24 ms 42836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 42580 KB Output isn't correct
2 Halted 0 ms 0 KB -