oj.uz

Submission #93869

# Submission time Handle Problem Language Result Execution time Memory
93869 2019-01-12T15:31:02 Z igzi Ruka (COI15_ruka) C++17
100 / 100
 629 ms 411928 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 400760 KB Output is correct
2 Correct 404 ms 400900 KB Output is correct
3 Correct 399 ms 400760 KB Output is correct
4 Correct 409 ms 400816 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 400760 KB Output is correct
2 Correct 404 ms 400900 KB Output is correct
3 Correct 399 ms 400760 KB Output is correct
4 Correct 409 ms 400816 KB Output is correct
5 Correct 498 ms 404088 KB Output is correct
6 Correct 486 ms 403576 KB Output is correct
7 Correct 510 ms 404092 KB Output is correct
8 Correct 507 ms 404016 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 400760 KB Output is correct
2 Correct 404 ms 400900 KB Output is correct
3 Correct 399 ms 400760 KB Output is correct
4 Correct 409 ms 400816 KB Output is correct
5 Correct 498 ms 404088 KB Output is correct
6 Correct 486 ms 403576 KB Output is correct
7 Correct 510 ms 404092 KB Output is correct
8 Correct 507 ms 404016 KB Output is correct
9 Correct 629 ms 410892 KB Output is correct
10 Correct 625 ms 411928 KB Output is correct
11 Correct 604 ms 410456 KB Output is correct
12 Correct 612 ms 410368 KB Output is correct