| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 251895 |
2020-07-23T03:03:25 Z |
racsosabe |
Ruka (COI15_ruka) |
C++14 |
|
369 ms |
11744 KB |
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;
const long double PI = acos(-1);
const long long MOD = 1000000000 +7;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}
ll add(ll a, ll b, ll m = MOD){
if(a >= m) a %= m;
if(b >= m) b %= m;
if(a < 0) a += m;
if(b < 0) b += m;
ll res = a+b;
if(res >= m or res <= -m) res %= m;
if(res < 0) res += m;
return res;
}
ll mul(ll a, ll b, ll m = MOD){
if(a >= m) a %= m;
if(b >= m) b %= m;
if(a < 0) a += m;
if(b < 0) b += m;
ll res = a*b;
if(res >= m or res <= -m) res %= m;
if(res < 0) res += m;
return res;
}
ll pow_mod(ll a, ll b, ll m = MOD){
ll res = 1LL;
a = a%m;
while(b){
if(b&1) res = mul(res,a,m);
b >>= 1;
a = mul(a,a,m);
}
return res;
}
ll fastexp(ll a, ll b){
ll res = 1LL;
while(b){
if(b&1) res = res*a;
b >>= 1;
a *= a;
}
return res;
}
int gcdExtendido(int a, int b, int *x, int *y){
if(a == 0){
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtendido(b%a,a,&x1,&y1);
*x = y1-(b/a)*x1;
*y = x1;
return gcd;
}
int modInverso(int a, int m){
int x, y;
int g = gcdExtendido(a,m,&x,&y);
if(g!=1) return -1;
else return (x%m + m)%m;
}
/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/
struct DSegTree{
int xmin;
int xmax;
int nodes;
vector<int> st, L, R;
DSegTree(){
xmin = -500 * 100000 - 5;
xmax = 500 * 100000 + 5;
nodes = 0;
st.clear();
L.clear();
R.clear();
addNode();
}
void addNode(){
st.emplace_back(0);
L.emplace_back(-1);
R.emplace_back(-1);
nodes += 1;
}
void update(int x, int y, int pos, int l, int r){
if(l == r){
st[pos] += y;
return;
}
int mi = l + (r - l) / 2;
if(l <= x and x <= mi){
if(L[pos] == -1){
L[pos] = nodes;
addNode();
}
update(x, y, L[pos], l, mi);
}
else{
if(R[pos] == -1){
R[pos] = nodes;
addNode();
}
update(x, y, R[pos], mi+1, r);
}
st[pos] = (L[pos] >= 0? st[L[pos]] : 0) + (R[pos] >= 0? st[R[pos]] : 0);
}
int query(int x, int y, int pos, int l, int r){
if(y < l or r < x or x > y or pos == -1) return 0;
if(x <= l and r <= y) return st[pos];
int mi = l + (r - l) / 2;
return query(x, y, L[pos], l, mi) + query(x, y, R[pos], mi+1, r);
}
int query(int y){
return query(xmin, y, 0, xmin, xmax);
}
void update(int x, int y){
update(x, y, 0, xmin, xmax);
}
};
struct Dim{
int D;
DSegTree S;
stack<int> P;
Dim(){
D = 0;
};
void init(vector<int> X){
for(int i = X.size() - 1; i >= 0; i--){
P.emplace(X[i]);
S.update(X[i], 1);
}
}
int pop(){
int val = P.top();
P.pop();
S.update(val, -1);
return val;
}
void push(int val){
P.emplace(val - D);
S.update(val - D, 1);
}
void updateD(int val){
D += val;
}
int query(){
return S.query(-D-1);
}
};
const int N = 100000+5;
int n, m;
int P = 0;
Dim Lx, Hx;
Dim Ly, Hy;
int ft[3][N];
int cursor = 1;
int x[N], y[N];
void update(int id, int pos, int val){
pos++;
while(pos <= n + 1){
ft[id][pos] += val;
pos += (-pos) & pos;
}
}
int getSum(int id, int pos){
pos++;
int res = 0;
while(pos > 0){
res += ft[id][pos];
pos &= pos-1;
}
return res;
}
void change(int i, int signo = 1){
int s_i = getSum(0, i);
int s_ip = getSum(0, i + 1);
if(min(s_i, s_ip) < 0 and max(s_i, s_ip) > 0){
P += signo;
}
s_i = getSum(1, i);
s_ip = getSum(1, i + 1);
if(min(s_i, s_ip) < 0 and max(s_i, s_ip) > 0){
P += signo;
}
}
void init(){
for(int i = 0; i <= n; i++){
update(0, i, x[i]);
update(1, i, y[i]);
}
vector<int> lx;
vector<int> hx;
for(int i = 1; i + 1 <= n; i++){
int s_i = getSum(0, i);
int s_ip = getSum(0, i + 1);
lx.emplace_back(min(s_i, s_ip));
hx.emplace_back(max(s_i, s_ip));
}
Lx.init(lx);
Hx.init(hx);
vector<int> ly;
vector<int> hy;
for(int i = 1; i + 1 <= n; i++){
int s_i = getSum(1, i);
int s_ip = getSum(1, i + 1);
ly.emplace_back(min(s_i, s_ip));
hy.emplace_back(max(s_i, s_ip));
}
Ly.init(ly);
Hy.init(hy);
change(0, 1);
}
void moveRight(){
if(cursor + 1 <= n){
change(cursor, 1);
Lx.pop();
Hx.pop();
Ly.pop();
Hy.pop();
cursor += 1;
}
}
void moveLeft(){
if(cursor - 1 >= 1){
change(cursor - 1, -1);
Lx.push(min(getSum(0, cursor), getSum(0, cursor-1)));
Hx.push(max(getSum(0, cursor), getSum(0, cursor-1)));
Ly.push(min(getSum(1, cursor), getSum(1, cursor-1)));
Hy.push(max(getSum(1, cursor), getSum(1, cursor-1)));
cursor -= 1;
}
}
void modify(int nx, int ny){
int lastx = x[cursor];
int lasty = y[cursor];
if(cursor - 1 >= 0){
change(cursor - 1, -1);
}
update(0, cursor, nx - lastx);
update(1, cursor, ny - lasty);
if(cursor - 1 >= 0){
change(cursor - 1, 1);
}
Lx.updateD(nx - lastx);
Hx.updateD(nx - lastx);
Ly.updateD(ny - lasty);
Hy.updateD(ny - lasty);
x[cursor] = nx;
y[cursor] = ny;
}
int solve(){
return P + Lx.query() - Hx.query() + Ly.query() - Hy.query();
}
int main(){
ri(n);
x[0] = y[0] = 1;
for(int i = 1; i <= n; i++){
ri2(x[i], y[i]);
}
init();
ri(m);
int nx, ny;
while(m--){
char c = getchar();
while(!isalpha(c)) c = getchar();
if(c == 'B'){
moveLeft();
}
else if(c == 'F'){
moveRight();
}
else if(c == 'C'){
ri2(nx, ny);
modify(nx, ny);
}
else{
printf("%d\n", solve());
}
}
return 0;
}
Compilation message
ruka.cpp: In function 'int main()':
ruka.cpp:6:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ri(x) scanf("%d",&(x))
~~~~~^~~~~~~~~~~
ruka.cpp:318:2: note: in expansion of macro 'ri'
ri(n);
^~
ruka.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ri2(x,y) scanf("%d %d",&(x),&(y))
~~~~~^~~~~~~~~~~~~~~~~~~
ruka.cpp:321:3: note: in expansion of macro 'ri2'
ri2(x[i], y[i]);
^~~
ruka.cpp:6:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ri(x) scanf("%d",&(x))
~~~~~^~~~~~~~~~~
ruka.cpp:324:2: note: in expansion of macro 'ri'
ri(m);
^~
ruka.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ri2(x,y) scanf("%d %d",&(x),&(y))
~~~~~^~~~~~~~~~~~~~~~~~~
ruka.cpp:336:4: note: in expansion of macro 'ri2'
ri2(nx, ny);
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
116 ms |
4176 KB |
Output is correct |
| 6 |
Correct |
96 ms |
3884 KB |
Output is correct |
| 7 |
Correct |
124 ms |
3680 KB |
Output is correct |
| 8 |
Correct |
105 ms |
3680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
116 ms |
4176 KB |
Output is correct |
| 6 |
Correct |
96 ms |
3884 KB |
Output is correct |
| 7 |
Correct |
124 ms |
3680 KB |
Output is correct |
| 8 |
Correct |
105 ms |
3680 KB |
Output is correct |
| 9 |
Correct |
277 ms |
9664 KB |
Output is correct |
| 10 |
Correct |
369 ms |
11744 KB |
Output is correct |
| 11 |
Correct |
292 ms |
8292 KB |
Output is correct |
| 12 |
Correct |
319 ms |
11492 KB |
Output is correct |
