This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int SQ = 300;
int N, M;
ll X[MAXN+10], Y[MAXN+10];
struct Buc
{
ll off;
vector<ll> comp, val;
Buc()
{
off=0;
comp=val=vector<ll>();
}
};
ll init(int p, ll *A, Buc *B, ll off)
{
int l=max(1, p*SQ), r=min(N, p*SQ+SQ-1);
ll sum=0;
B[p]=Buc(); B[p].off=off;
vector<pll> V;
for(int j=l; j<=r; j++)
{
if(A[j]==0) continue;
ll tl=sum, tr=sum+A[j];
if(A[j]<0) tl--;
else tl++;
if(tl>tr) swap(tl, tr);
tr++;
V.push_back({tl, 1});
V.push_back({tr, -1});
B[p].comp.push_back(tl);
B[p].comp.push_back(tr);
sum+=A[j];
}
sort(B[p].comp.begin(), B[p].comp.end());
B[p].comp.erase(unique(B[p].comp.begin(), B[p].comp.end()), B[p].comp.end());
sort(V.begin(), V.end());
B[p].val.resize(B[p].comp.size());
ll t=0;
for(int i=0, j=0; i<B[p].comp.size(); i++)
{
for(; j<V.size() && V[j].first==B[p].comp[i]; j++) t+=V[j].second;
B[p].val[i]=t;
}
return sum;
}
void init(ll *A, Buc *B)
{
ll sum=1;
for(int i=0; i<=N/SQ; i++) sum+=init(i, A, B, sum);
}
int query(int p, Buc *B)
{
int it=upper_bound(B[p].comp.begin(), B[p].comp.end(), -B[p].off)-B[p].comp.begin()-1;
if(it<0) return 0;
return B[p].val[it];
}
int query(Buc *B)
{
int ans=0;
for(int i=0; i<=N/SQ; i++) ans+=query(i, B);
return ans;
}
void update(int p, ll *A, Buc *B, ll d)
{
ll sum=B[p/SQ].off;
sum+=init(p/SQ, A, B, sum);
for(int i=p/SQ+1; i<=N/SQ; i++) B[i].off+=d;
}
Buc BX[MAXN/SQ+10], BY[MAXN/SQ+10];
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++) scanf("%lld%lld", &X[i], &Y[i]);
init(X, BX);
init(Y, BY);
scanf("%d", &M);
int pos=1;
while(M--)
{
char c;
scanf(" %c", &c);
if(c=='B') pos=max(1, pos-1);
else if(c=='F') pos=min(N, pos+1);
else if(c=='Q') printf("%d\n", query(BX)+query(BY));
else
{
ll nx, ny;
scanf("%lld%lld", &nx, &ny);
ll dx=nx-X[pos], dy=ny-Y[pos];
X[pos]=nx; Y[pos]=ny;
update(pos, X, BX, dx);
update(pos, Y, BY, dy);
}
}
}
Compilation message (stderr)
ruka.cpp: In function 'll init(int, ll*, Buc*, ll)':
ruka.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0, j=0; i<B[p].comp.size(); i++)
| ~^~~~~~~~~~~~~~~~~
ruka.cpp:53:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(; j<V.size() && V[j].first==B[p].comp[i]; j++) t+=V[j].second;
| ~^~~~~~~~~
ruka.cpp: In function 'int main()':
ruka.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
ruka.cpp:91:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
91 | for(int i=1; i<=N; i++) scanf("%lld%lld", &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
96 | scanf("%d", &M);
| ~~~~~^~~~~~~~~~
ruka.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
ruka.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
108 | scanf("%lld%lld", &nx, &ny);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |