Submission #722685

#	Time	Username	Problem	Language	Result	Execution time	Memory
722685		victor_gao	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3062 ms	212516 KiB

street_lamps

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct BIT{
    int n;
    vector<int>arr;
    vector<int>have;
    void in(int x){ have.push_back(x); }
    void build(){
        sort(have.begin(),have.end());
        have.resize(unique(have.begin(),have.end())-have.begin());
        n=have.size();
        arr.resize(n+3);
    }
    int idx(int x){ 
        if (have.empty()) return 0;
        return upper_bound(have.begin(),have.end(),x)-have.begin();
    }
    void modify(int p,int c){
        if (p==0) return;
        for (;p<=n;p+=(p&-p))
            arr[p]+=c;
    }
    int query(int p){
        int ans=0;
        for (;p>0;p-=(p&-p))
            ans+=arr[p];
        return ans;
    }
};
struct BBIT{
    int n;
    vector<BIT>arr;
    void init(int _n){
        n=_n;
        arr.resize(n+3);
    }
    void need_use(int a,int b){
        for (;a<=n;a+=(a&-a))
            arr[a].in(b);
    }
    void modify(int a,int b,int c){
        for (;a<=n;a+=(a&-a))
            arr[a].modify(arr[a].idx(b),c);
    }
    int query(int a,int b){
        int ans=0;
        for (;a>0;a-=(a&-a))
            ans=(ans+arr[a].query(arr[a].idx(b)));
        return ans;
    }
}bit;
struct Query{
    int op,a,b;
    Query(int i,int j,int k):op(i),a(j),b(k){}
};
int n,q,last_time[N];
bool arr[N];
set<pair<pii,int> >all;
vector<Query>qry;
vector<pair<pii,int> >change[N];
void add_need(int a,int b){
    if (a>b) return;
    bit.need_use(a,a); bit.need_use(a,b+1);
    bit.need_use(b+1,a); bit.need_use(b+1,b+1);
}
signed main(){
    fast
    cin>>n>>q;
    bit.init(n);
    int l=1,val=-1;
    for (int i=1;i<=n;i++){
        char c; cin>>c;
        arr[i]=c-'0';
        if (arr[i]==val) continue;
        else {
            if (val==1) all.insert({{l,i-1},0});
            val=arr[i]; l=i;
        }
    }
    if (val==1)
        all.insert({{l,n},0});
    for (int i=1;i<=q;i++){
        string str;
        int a=0,b=0; cin>>str;
        if (str=="toggle"){
            cin>>a;
            qry.push_back(Query(1,a,a));
        }
        else {
            cin>>a>>b; b--;
            qry.push_back(Query(2,a,b));
            bit.need_use(a,b);
        }
    }
    for (int i=1;i<=q;i++){
        if (qry[i-1].op==1){
            int p=qry[i-1].a;
            if (arr[p]==1){
                auto it=all.upper_bound(pair<pii,int>(pii(p,1e9),1e9)); it--;
                auto [j,t]=(*it);
                change[i].push_back({{j.x,j.y},i-t});
                add_need(j.x,j.y);
                all.erase(it);
                if (j.x<=p-1) all.insert({{j.x,p-1},i});
                if (p+1<=j.y) all.insert({{p+1,j.y},i});
            }
            else {
                auto it=all.upper_bound(pair<pii,int>(pii(p,p),1e9));
                pii now={p,p};
                if (it!=all.end()){
                    if ((*it).x.x==p+1){
                        now.y=(*it).x.y;
                        change[i].push_back({(*it).x,i-(*it).y});
                        add_need((*it).x.x,(*it).x.y);
                        it=all.erase(it);
                    }
                }
                if (it!=all.begin()){
                    it=prev(it);
                    if ((*it).x.y==p-1){
                        now.x=(*it).x.x;
                        change[i].push_back({(*it).x,i-(*it).y});
                        add_need((*it).x.x,(*it).x.y);
                        it=all.erase(it);
                    }
                }
                all.insert({now,i});
            }
            arr[p]^=1;
        }
        else {
            int a=qry[i-1].a,b=qry[i-1].b;
            auto it=all.upper_bound(pair<pii,int>(pii(a,1e9),1e9));
            if (it==all.begin()){
                last_time[i]=i;
                continue;
            }
            it--;
            if ((*it).x.x<=a&&(*it).x.y>=b) last_time[i]=(*it).y;
            else last_time[i]=i;
        }
    }
    for (int i=0;i<=n+1;i++)
        bit.arr[i].build();
    for (int i=1;i<=q;i++){
        if (qry[i-1].op==1){
            for (auto [j,t]:change[i]){
               // cout<<"change "<<j.x<<' '<<j.y<<" "<<t<<'\n';
                bit.modify(j.x,j.x,t);
                bit.modify(j.x,j.y+1,-t);
                bit.modify(j.y+1,j.x,-t);
                bit.modify(j.y+1,j.y+1,t);
            }
        }
        else {
            cout<<bit.query(qry[i-1].a,qry[i-1].b)+i-last_time[i]<<'\n';
        }
    }
}
/*
5 7
11111
query 1 2
toggle 4
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20