Submission #93865

#	Time	Username	Problem	Language	Result	Execution time	Memory
93865		igzi	Ruka (COI15_ruka)	C++17	9 / 100	511 ms	395912 KiB

ruka

#include <bits/stdc++.h>
#define maxN 100005
#define maxC 501

using namespace std;

int f[2*maxN*maxC],n,m,i,x[maxN],y[maxN],z[maxN],s,p,q,t,tmp;
vector <int> ans(maxN,0);
stack <int> h;

struct query{
char c;
int x,y;
};

query k[maxN];

void update(int p,int v){
//cout<<p<<" "<<v<<endl;
p+=maxN*maxC;
while(p<2*maxN*maxC){
    f[p]+=v;
    p+=p & (-p);
}
}

int query(int p){
p+=maxN*maxC;
int ans=0;
while(p>0){
ans+=f[p];
p-=p & -p;
}
return ans;
}

void resi(){
for(i=0;i<2*maxN*maxC;i++) f[i]=0;
s=1;
for(i=0;i<n;i++){
update(s+min(y[i],0),1);
update(s+max(y[i],0),-1);  
s+=y[i];
}
tmp=s;
s--;
t=q=p=0;
for(i=0;i<m;i++){
if(k[i].c=='Q'){
    ans[q]+=query(-t);
    q++;
}
if(k[i].c=='F'){
    if(p==n-1) continue;
    update(tmp-s+min(0,y[p]),-1);
    update(tmp-s+max(0,y[p]),1);
    s-=y[p];
    p++;
}
if(k[i].c=='B'){
    if(p==0) continue;
    s+=y[p-1];
    update(tmp-s+min(0,y[p-1]),1);
    update(tmp-s+max(0,y[p-1]),-1);
    p--;
}
if(k[i].c=='C'){
    update(tmp-s+min(0,y[p]),-1);
    update(tmp-s+max(0,y[p]),1);
    t+=k[i].y-y[p];
    s+=k[i].y-y[p];
    y[p]=k[i].y;
    update(tmp-s+min(0,y[p]),1);
    update(tmp-s+max(0,y[p]),-1);
}
}
while(h.size()) h.pop();
s=1;
t=p=q=0;
for(i=0;i<m;i++){
if(k[i].c=='Q'){
    ans[q]+=t;
    q++;
}
if(k[i].c=='F'){
    if(p==n-1) continue;
    h.push(s);
    s+=z[p];
    if(h.top()*s<0) t++;
    p++;
}
if(k[i].c=='B'){
    if(p==0) continue;
    if(h.size() && h.top()*s<0) t--;
    h.pop();
    s-=z[p-1];
    p--;
}
if(k[i].c=='C'){
    z[p]=k[i].y;
}
}
}

int main(){
cin>>n;
for(i=0;i<n;i++) {cin>>x[i]>>y[i]; z[i]=y[i];}
cin>>m;
for(i=0;i<m;i++){
    char c;
    int a,b;
    a=b=0;
    cin>>c;
    k[i].c=c;
    if(k[i].c=='C') cin>>a>>b;
    k[i].x=a;
    k[i].y=b;
}
resi();
for(i=0;i<n;i++) {swap(x[i],y[i]); z[i]=y[i];}
for(i=0;i<m;i++){
    if(k[i].c=='C') swap(k[i].x,k[i].y);
}
resi();
for(i=0;i<q;i++) cout<<ans[i]<<endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 35
• Subtask 3: 0 / 56