Submission #859375

#	Time	Username	Problem	Language	Result	Execution time	Memory
859375		winter0101	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1365 ms	89204 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=3e5+9;
vector<int>node[maxn];
vector<long long>bit[maxn];
int n,q;
void fakeupdate(int x,int y){
for(;x<=n;x+=(x-(x&(x-1)))){
node[x].pb(y);
}
}
void fakeget(int x,int y){
for(;x>=1;x-=(x-(x&(x-1)))){
node[x].pb(y);
}
}
void build(){
for1(i,1,n){
sort(all(node[i]));
auto it=unique(all(node[i]));
node[i].resize(distance(node[i].begin(),it));
bit[i].resize(sz(node[i]));
}
}
void update(int x,int y,int val){
for(;x<=n;x+=(x-(x&(x-1)))){
    for(int yy=lower_bound(all(node[x]),y)-node[x].begin();yy<sz(node[x]);yy+=(yy-(yy&(yy-1)))){
    bit[x][yy]+=val;
    }
}
}
long long get(int x,int y){
long long sum=0;
for(;x>=1;x-=(x-(x&(x-1)))){
    for(int yy=lower_bound(all(node[x]),y)-node[x].begin();yy>=1;yy-=(yy-(yy&(yy-1)))){
    sum+=bit[x][yy];
    }
}
return sum;
}
struct line{
int l,r,t;
bool operator <(const line &p)const{
return r<p.r;
}
};
struct query{
int type,x,y;
}b[maxn];
void fakerect(int x1,int y1,int x2,int y2){
fakeget(x1-1,y1-1);
fakeget(x2,y2);
fakeget(x2,y1-1);
fakeget(x1-1,y2);
}
long long getrect(int x1,int y1,int x2,int y2){
return get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    string s;
    cin>>s;
    s=" "+s;
    for1(i,1,n)node[i].pb(0);
    multiset<line>nt;
    for1(i,1,n){
    if (s[i]=='0')continue;
    else {
    int p=i;
    for1(j,i,n){
    if (s[j]!=s[i])break;
    p=j;
    }
    nt.insert({i,p,1});
    i=p;
    }
    }
    string t=s;
    for1(i,1,q){
    //cin>>b[i].type;
    string quest;
    cin>>quest;
    if (quest=="query")b[i].type=1;
    else b[i].type=2;
    if (b[i].type==1){
    cin>>b[i].x>>b[i].y;
    if (b[i].x>b[i].y)swap(b[i].x,b[i].y);
    if (b[i].x==b[i].y)continue;
    b[i].y--;
    //small than x and large than y
    fakerect(1,b[i].y,b[i].x,n);
    }
    else {
    cin>>b[i].x;
    if (s[b[i].x]=='1'){
    s[b[i].x]='0';
    auto it=nt.lower_bound({b[i].x,b[i].x,-1});
    line temp=(*it);
    fakeupdate(temp.l,temp.r);
    nt.erase(it);
    if (temp.l<b[i].x){
    nt.insert({temp.l,b[i].x-1,i});
    }
    if (temp.r>b[i].x){
    nt.insert({b[i].x+1,temp.r,i});
    }
    }
    else {
    s[b[i].x]='1';
    auto it=nt.upper_bound({b[i].x,b[i].x,-1});
    line nw={b[i].x,b[i].x,i};
    if (it!=nt.begin()){
    it--;
    line temp=(*it);
    if (temp.r+1==b[i].x){
    nt.erase(it);
    fakeupdate(temp.l,temp.r);
    nw.l=temp.l;
    }
    }
    it=nt.upper_bound({b[i].x,b[i].x,-1});
    if (it!=nt.end()){
    line temp=(*it);
    if (temp.l==b[i].x+1){
    nt.erase(it);
    fakeupdate(temp.l,temp.r);
    nw.r=temp.r;
    }
    }
    nt.insert(nw);
    }
    }
    }
    build();
    s=t;
    nt.clear();
    for1(i,1,n){
    if (s[i]=='0')continue;
    else {
    int p=i;
    for1(j,i,n){
    if (s[j]!=s[i])break;
    p=j;
    }
    nt.insert({i,p,0});
    i=p;
    }
    }
    for1(i,1,q){
    if (b[i].type==1){
    //cout<<b[i].x<<" "<<b[i].y<<'\n';
    if (b[i].x>b[i].y){
    cout<<i<<'\n';
    continue;
    }
    //small than x and large than y
    long long ans=getrect(1,b[i].y,b[i].x,n);
    auto it=nt.lower_bound({b[i].x,b[i].y,-1});
    if (it!=nt.end()){
    auto temp=(*it);
    if (temp.r>=b[i].y&&temp.l<=b[i].x){
    ans+=i-temp.t;
    //cout<<temp.l<<" "<<temp.r<<" "<<b[i].x<<" "<<b[i].y<<" "<<temp.t<<" "<<ans<<'\n';
    }
    }
    cout<<ans<<'\n';
    }
    else {
    if (s[b[i].x]=='1'){
    s[b[i].x]='0';
    auto it=nt.lower_bound({b[i].x,b[i].x,-1});
    line temp=(*it);
    update(temp.l,temp.r,i-temp.t);
    nt.erase(it);
    if (temp.l<b[i].x){
    nt.insert({temp.l,b[i].x-1,i});
    }
    if (temp.r>b[i].x){
    nt.insert({b[i].x+1,temp.r,i});
    }
    }
    else {
    s[b[i].x]='1';
    auto it=nt.upper_bound({b[i].x,b[i].x,-1});
    line nw={b[i].x,b[i].x,i};
    if (it!=nt.begin()){
    it--;
    line temp=(*it);
    if (temp.r+1==b[i].x){
    nt.erase(it);
    update(temp.l,temp.r,i-temp.t);
    nw.l=temp.l;
    }
    }
    it=nt.upper_bound({b[i].x,b[i].x,-1});
    if (it!=nt.end()){
    line temp=(*it);
    if (temp.l==b[i].x+1){
    nt.erase(it);
    update(temp.l,temp.r,i-temp.t);
    nw.r=temp.r;
    }
    }
    nt.insert(nw);
    }
    }
    }



}

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