oj.uz

답안 #283831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283831 2020-08-26T07:44:35 Z 임성재(#5753) Ruka (COI15_ruka) C++17
9 / 100
 2000 ms 2728 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const ll inf = 1e9 + 7;
const int sz = 230;

int n, m, ans;
pii idx[sz * sz + 100];
int x[sz * sz + 100];
int y[sz * sz + 100];
int xh[sz+1];
int yh[sz+1];
int X[sz+1][sz+1], Y[sz+1][sz+1];
vector<pii> xans[sz+1], yans[sz+1];

void upd(int t) {
	int k = lower_bound(all(xans[t]), mp(xh[t], 0)) - xans[t].begin() - 1;
	ans -= xans[t][k].se;
	k = lower_bound(all(yans[t]), mp(yh[t], 0)) - yans[t].begin() - 1;
	ans -= yans[t][k].se;

	vector<pii> v;

	for(int i=1; i<sz; i++) {
		v.eb(min(X[t][i-1], X[t][i]), 1);
		v.eb(max(X[t][i-1], X[t][i]), -1);
	}

	sort(all(v));

	xans[t].clear();
	xans[t].eb(-inf, 0);

	int sum = 0;
	for(int i = 0; i < v.size(); ) {
		int j = i;
		while(j < v.size() && v[i].fi == v[j].fi) {
			sum += v[j].se;
			j++;
		}

		xans[t].eb(v[i].fi, sum);

		i = j;
	}

	v.clear();

	for(int i=1; i<sz; i++) {
		v.eb(min(Y[t][i-1], Y[t][i]), 1);
		v.eb(max(Y[t][i-1], Y[t][i]), -1);
	}

	sort(all(v));

	yans[t].clear();
	yans[t].eb(-inf, 0);

	sum = 0;
	for(int i = 0; i < v.size(); ) {
		int j = i;
		while(j < v.size() && v[i].fi == v[j].fi) {
			sum += v[j].se;
			j++;
		}

		yans[t].eb(v[i].fi, sum);

		i = j;
	}

	k = lower_bound(all(xans[t]), mp(xh[t], 0)) - xans[t].begin() - 1;
	ans += xans[t][k].se;
	k = lower_bound(all(yans[t]), mp(yh[t], 0)) - yans[t].begin() - 1;
	ans += yans[t][k].se;
}

int main() {
	fast;

	cin >> n;

	for(int i=1; i <= sz * sz - 1; i++) {
		idx[i] = idx[i-1];

		if(i % sz == 0) idx[i].fi++, idx[i].se = 0;
		else idx[i].se++;
	}

	X[0][0] = Y[0][0] = 1;

	for(int i=1; i <= sz * sz - 1; i++) {
		if(i <= n) cin >> x[i] >> y[i];

		X[idx[i].fi][idx[i].se] = X[idx[i-1].fi][idx[i-1].se] + x[i];
		Y[idx[i].fi][idx[i].se] = Y[idx[i-1].fi][idx[i-1].se] + y[i];
	}

	for(int i=0; i<sz; i++) {
		xans[i].eb(-inf, 0);
		yans[i].eb(-inf, 0);
		
		upd(i);
	}

	cin >> m;

	int cur = 1;

	while(m--) {
		char c;
		cin >> c;

		if(c == 'B') cur = max(1, cur - 1);
		else if(c == 'F') cur = min(n, cur + 1);
		else if(c == 'Q') {
			int ret = 0;
			for(int i = 0; i < sz; i++) {
				if(i && (ll) (X[i][0] - xh[i]) * (X[i-1][sz-1] - xh[i-1]) < 0) ret++;
				if(i && (ll) (Y[i][0] - yh[i]) * (Y[i-1][sz-1] - yh[i-1]) < 0) ret++;
			}

			cout << ans + ret << "\n";
		}
		else {
			int dx = -x[cur];
			int dy = -y[cur];
			
			cin >> x[cur] >> y[cur];

			dx += x[cur];
			dy += y[cur];

			for(int i = idx[cur-1].fi + 1; i < sz; i++) {
				int k = lower_bound(all(xans[i]), mp(xh[i], 0)) - xans[i].begin() - 1;
				ans -= xans[i][k].se;
				k = lower_bound(all(yans[i]), mp(yh[i], 0)) - yans[i].begin() - 1;
				ans -= yans[i][k].se;

				xh[i] -= dx;
				yh[i] -= dy;

				k = lower_bound(all(xans[i]), mp(xh[i], 0)) - xans[i].begin() - 1;
				ans += xans[i][k].se;
				k = lower_bound(all(yans[i]), mp(yh[i], 0)) - yans[i].begin() - 1;
				ans += yans[i][k].se;
			}

			for(int i = idx[cur-1].se + 1; i < sz; i++) {
				X[idx[cur-1].fi][i] += dx;
				Y[idx[cur-1].fi][i] += dy;
			}

			upd(idx[cur-1].fi);
		}
	}
}

Compilation message

ruka.cpp: In function 'void upd(int)':
ruka.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 0; i < v.size(); ) {
      |                 ~~^~~~~~~~~~
ruka.cpp:49:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while(j < v.size() && v[i].fi == v[j].fi) {
      |         ~~^~~~~~~~~~
ruka.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0; i < v.size(); ) {
      |                 ~~^~~~~~~~~~
ruka.cpp:74:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   while(j < v.size() && v[i].fi == v[j].fi) {
      |         ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1152 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 54 ms 1280 KB Output is correct
4 Correct 43 ms 1288 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1152 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 54 ms 1280 KB Output is correct
4 Correct 43 ms 1288 KB Output is correct
5 Correct 1910 ms 2728 KB Output is correct
6 Execution timed out 2052 ms 1932 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 1152 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 54 ms 1280 KB Output is correct
4 Correct 43 ms 1288 KB Output is correct
5 Correct 1910 ms 2728 KB Output is correct
6 Execution timed out 2052 ms 1932 KB Time limit exceeded
7 Halted 0 ms 0 KB -