oj.uz

Submission #27267

# Submission time Handle Problem Language Result Execution time Memory
27267 2017-07-12T05:29:01 Z 상수조아(#1141) Ruka (COI15_ruka) C++11
100 / 100
 396 ms 11120 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int N, M;
int X[2][100010];
struct node{
	node(){}
	node(int v):v(v){child[0] = child[1] = 0;}
	int v;
	node *child[2];
	void update(int l, int r, int s, int d, int vv) {
		if(s <= l && r <= d) {
			v += vv;
			return;
		}
		int m = (l + r) >> 1;
		if(s <= m) {
			if(!child[0]) child[0] = new node(0);
			child[0]->update(l, m, s, d, vv);
		}
		if(m < d) {
			if(!child[1]) child[1] = new node(0);
			child[1]->update(m+1, r, s, d, vv);
		}
	}
	void update(int s, int d, int vv) {
		if(s > d) swap(s, d);
		update(-6e7, 6e7, s, d, vv);
	}
	int read(int x) {
		return read(-6e7, 6e7, x);
	}
	int read(int l, int r, int x) {
		if(l == r) return v;
		int res = v;
		int m = (l + r) >> 1;
		if(x <= m) res += (child[0] ? child[0]->read(l, m, x) : 0);
		else res += (child[1] ? child[1]->read(m+1, r, x) : 0);
		return res;
	}
}T[2];

void solve(){
	scanf("%d", &N);
	rep(i, N) scanf("%d%d", X[0]+i, X[1]+i);
	int now[2] = {1, 1};
	rep(i, N) {
		rep(u, 2) {
			int l = now[u];
			int r = l + X[u][i];
			T[u].update(l, r, 1);
			now[u] = r;
		}
	}
	int pos = 0, ans = 0, delta[2] = {};
	now[0] = now[1] = 1;
	scanf("%d", &M);
	rep(i, M) {
		char c; scanf(" %c", &c);
		if(c == 'C') {
			int nx[2]; scanf("%d%d", nx, nx+1);
			rep(u, 2) {
				int start = now[u] - delta[u];
				T[u].update(start, start + X[u][pos], -1);
				T[u].update(start + X[u][pos] - nx[u], start + X[u][pos], 1);
				delta[u] -= X[u][pos] - nx[u];
				X[u][pos] = nx[u];
			}
		}
		else if(c == 'Q') {
			int res = ans;
			rep(u, 2) res += T[u].read(-delta[u]);
			printf("%d\n", res);
		}
		else if(c == 'F') {
			if(pos == N-1) continue;
			rep(u, 2) {
				if((now[u] < 0) ^ (now[u] + X[u][pos] < 0)) ++ans;
				int start = now[u] - delta[u];
				T[u].update(start, start + X[u][pos], -1);
				now[u] += X[u][pos];
			}
			++pos;
		}
		else {
			if(pos == 0) continue;
			rep(u, 2) {
				if((now[u] < 0) ^ (now[u] - X[u][pos - 1] < 0)) --ans;
				int start = now[u] - delta[u];
				T[u].update(start, start - X[u][pos - 1], 1);
				now[u] -= X[u][pos - 1];
			}
			--pos;
		}
	}
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
};

Compilation message

ruka.cpp: In function 'void solve()':
ruka.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
ruka.cpp:74:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, N) scanf("%d%d", X[0]+i, X[1]+i);
                                         ^
ruka.cpp:86:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
                 ^
ruka.cpp:88:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
                           ^
ruka.cpp:90:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int nx[2]; scanf("%d%d", nx, nx+1);
                                      ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2936 KB Output is correct
2 Correct 0 ms 2936 KB Output is correct
3 Correct 3 ms 2936 KB Output is correct
4 Correct 0 ms 2936 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2936 KB Output is correct
2 Correct 0 ms 2936 KB Output is correct
3 Correct 3 ms 2936 KB Output is correct
4 Correct 0 ms 2936 KB Output is correct
5 Correct 123 ms 4784 KB Output is correct
6 Correct 119 ms 6368 KB Output is correct
7 Correct 116 ms 2936 KB Output is correct
8 Correct 136 ms 2936 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2936 KB Output is correct
2 Correct 0 ms 2936 KB Output is correct
3 Correct 3 ms 2936 KB Output is correct
4 Correct 0 ms 2936 KB Output is correct
5 Correct 123 ms 4784 KB Output is correct
6 Correct 119 ms 6368 KB Output is correct
7 Correct 116 ms 2936 KB Output is correct
8 Correct 136 ms 2936 KB Output is correct
9 Correct 329 ms 10592 KB Output is correct
10 Correct 396 ms 11120 KB Output is correct
11 Correct 319 ms 7160 KB Output is correct
12 Correct 339 ms 8612 KB Output is correct