Submission #93869

#	Time	Username	Problem	Language	Result	Execution time	Memory
93869		igzi	Ruka (COI15_ruka)	C++17	100 / 100	629 ms	411928 KiB

ruka

#include <bits/stdc++.h>
#define maxN 100100
#define maxC 510
 
using namespace std;
 
long long n,m,i,s,p,q,t,tmp;
int f[2*maxN*maxC],x[maxN],y[maxN],z[maxN];
vector <long long> ans(maxN,0);
stack <long long> h;
 
struct query{
char c;
long long x,y;
};
 
query k[3*maxN];
 
void update(long long p,long long v){
//cout<<p<<" "<<v<<endl;
p+=maxN*maxC;
while(p<2*maxN*maxC){
    f[p]+=v;
    p+=p & (-p);
}
}
 
long long query(long long p){
p+=maxN*maxC;
long long ans=0;
while(p>0){
ans+=f[p];
p-=p & -p;
}
return ans;
}
 
void resi(){
long long i;
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(){
std::ios_base::sync_with_stdio(false);
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: 35 / 35
• Subtask 3: 56 / 56