| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283723 |
2020-08-26T06:10:16 Z |
송준혁(#5751) |
Ruka (COI15_ruka) |
C++17 |
|
1773 ms |
24192 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, Q;
int Px, Py, Ox, Oy;
int Ax[101010], Ay[101010], num=1;
int ans[303030];
struct BIT{
int b=0;
vector<int> T;
void init(int n, int _b){T.resize(n+5); b=_b;}
void upd(int k, int v){for(;k<T.size();k+=k&-k)T[k]+=v;}
int f(int k){int r=0; for(;k;k^=k&-k)r+=T[k]; return r+b;}
} X, Y, F;
struct qry{int t, x, y;};
vector<qry> Qx, Qy, E;
vector<int> comp;
inline int id(int x){return (int)(lower_bound(all(comp), x)-comp.begin()+1);}
void sweep(){
sort(all(E), [&](qry a, qry b){return a.x < b.x;});
for (qry p : E){
if (p.t <= 1) F.upd(id(-p.y), p.t);
else ans[p.t-1] += F.f(id(-p.y));
}
for (qry p : E) if (p.t <= 1) F.upd(id(-p.y), -p.t);
}
void DNC(int s, int e){
if (s == e) return;
int m=s+e>>1;
for (int i=s; i<=m; i++) if (Qx[i].t <= 1) E.pb(Qx[i]);
for (int i=m+1; i<=e; i++) if (Qx[i].t > 1) E.pb(Qx[i]);
sweep();
E.clear();
DNC(s, m), DNC(m+1, e);
}
int main(){
scanf("%d", &N);
X.init(N, 1), Y.init(N, 1);
for (int i=1; i<=N; i++){
scanf("%d %d", &Ax[i], &Ay[i]);
X.upd(i, Ax[i]), Y.upd(i, Ay[i]);
if (i>1){
Qx.pb((qry){1, min(X.f(i-1), X.f(i)), max(X.f(i-1), X.f(i))});
Qy.pb((qry){1, min(Y.f(i-1), Y.f(i)), max(Y.f(i-1), Y.f(i))});
}
else Px = Ax[i] < 0, Py = Ay[i] < 0;
}
int t=1;
scanf("%d", &Q);
while (Q--){
char ch;
int vx, vy;
scanf(" %c", &ch);
if (ch == 'Q'){
ans[num++] = Px + Py;
Qx.pb((qry){num, Ox, Ox});
Qy.pb((qry){num, Oy, Oy});
}
if (ch == 'B'){
if (t == 1) continue;
if (min(X.f(t-1), X.f(t))<0 && max(X.f(t-1), X.f(t))>0) Px--;
if (min(Y.f(t-1), Y.f(t))<0 && max(Y.f(t-1), Y.f(t))>0) Py--;
Qx.pb((qry){1, min(X.f(t-1), X.f(t))+Ox, max(X.f(t-1), X.f(t))+Ox});
Qy.pb((qry){1, min(Y.f(t-1), Y.f(t))+Oy, max(Y.f(t-1), Y.f(t))+Oy});
t--;
}
if (ch == 'F'){
if (t == N) continue;
if (min(X.f(t+1), X.f(t))<0 && max(X.f(t+1), X.f(t))>0) Px++;
if (min(Y.f(t+1), Y.f(t))<0 && max(Y.f(t+1), Y.f(t))>0) Py++;
Qx.pb((qry){-1, min(X.f(t+1), X.f(t))+Ox, max(X.f(t+1), X.f(t))+Ox});
Qy.pb((qry){-1, min(Y.f(t+1), Y.f(t))+Oy, max(Y.f(t+1), Y.f(t))+Oy});
t++;
}
if (ch == 'C'){
scanf("%d %d", &vx, &vy);
if (min(X.f(t-1), X.f(t))<0 && max(X.f(t-1), X.f(t))>0) Px--;
if (min(Y.f(t-1), Y.f(t))<0 && max(Y.f(t-1), Y.f(t))>0) Py--;
Qx.pb((qry){-1, min(X.f(t+1), X.f(t))+Ox, max(X.f(t+1), X.f(t))+Ox});
Qy.pb((qry){-1, min(Y.f(t+1), Y.f(t))+Oy, max(Y.f(t+1), Y.f(t))+Oy});
X.upd(t,-Ax[t]+vx), Y.upd(t,-Ay[t]+vy);
Ox += Ax[t]-vx, Oy += Ay[t]-vy;
Ax[t] = vx, Ay[t] = vy;
if (min(X.f(t-1), X.f(t))<0 && max(X.f(t-1), X.f(t))>0) Px++;
if (min(Y.f(t-1), Y.f(t))<0 && max(Y.f(t-1), Y.f(t))>0) Py++;
Qx.pb((qry){1, min(X.f(t+1), X.f(t))+Ox, max(X.f(t+1), X.f(t))+Ox});
Qy.pb((qry){1, min(Y.f(t+1), Y.f(t))+Oy, max(Y.f(t+1), Y.f(t))+Oy});
}
}
for (int xy=1; xy<=2; xy++){
comp.clear();
for (qry p : Qx) comp.pb(-p.y);
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
F.init(comp.size(), 0);
DNC(0, Qx.size()-1);
swap(Qx, Qy);
}
for (int i=1; i<num; i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message
ruka.cpp: In member function 'void BIT::upd(int, int)':
ruka.cpp:17:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | void upd(int k, int v){for(;k<T.size();k+=k&-k)T[k]+=v;}
| ~^~~~~~~~~
ruka.cpp: In function 'void DNC(int, int)':
ruka.cpp:38:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m=s+e>>1;
| ~^~
ruka.cpp: In function 'int main()':
ruka.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
ruka.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
50 | scanf("%d %d", &Ax[i], &Ay[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
59 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
ruka.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
63 | scanf(" %c", &ch);
| ~~~~~^~~~~~~~~~~~
ruka.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | scanf("%d %d", &vx, &vy);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
552 ms |
10176 KB |
Output is correct |
| 6 |
Correct |
448 ms |
8976 KB |
Output is correct |
| 7 |
Correct |
538 ms |
10904 KB |
Output is correct |
| 8 |
Correct |
554 ms |
11032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
552 ms |
10176 KB |
Output is correct |
| 6 |
Correct |
448 ms |
8976 KB |
Output is correct |
| 7 |
Correct |
538 ms |
10904 KB |
Output is correct |
| 8 |
Correct |
554 ms |
11032 KB |
Output is correct |
| 9 |
Correct |
1502 ms |
22524 KB |
Output is correct |
| 10 |
Correct |
1773 ms |
24192 KB |
Output is correct |
| 11 |
Correct |
1511 ms |
22472 KB |
Output is correct |
| 12 |
Correct |
1532 ms |
22524 KB |
Output is correct |
