oj.uz

답안 #521815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521815 2022-02-03T08:29:59 Z ntabc05101 Ruka (COI15_ruka) C++14
100 / 100
 1106 ms 30940 KB 
#include<bits/stdc++.h>
using namespace std;

#define taskname ""

const int mxN = 100005;
const int off_set = 5e7;
const int mxX = 1e8 + 5;

int n, m;
int x[mxN], y[mxN], sumx, sumy;
int crl;

struct BIT {
	unordered_map<int, int> bits;

	void upd(int x, int dlt) {
		for (x += off_set; x < mxX; x += x & -x) {
			bits[x] += dlt;
		}
	}

	int get(int x) {
		int res = 0;
		for (x += off_set; x; x &= x - 1) {
			res += bits[x];
		}
		return res;
	}
} pLx, pHx, sLx, sHx, pLy, pHy, sLy, sHy;

void upd(BIT &L, BIT &H, int a, int b, int dlt) {
	if (a < b) {
		swap(a, b);
	}
	L.upd(b, dlt);
	H.upd(a, dlt);
}

void build(int x[], BIT &pL, BIT &pH, BIT &sL, BIT &sH) {
	for (int i = 1; i < 2; i++) {
		x[i] += x[i - 1];
		upd(pL, pH, x[i], x[i - 1], 1);
	}
	for (int i = 2, a, b; i <= n; i++) {
		x[i] += x[i - 1];
		upd(sL, sH, x[i], x[i - 1], 1);
	}
	/*for (int i = n; i; i--) {
		x[i] -= x[i - 1];
	}*/
} 

void bck() {
	if (crl > 1) {
		upd(pLx, pHx, x[crl], x[crl - 1], -1);
		upd(pLy, pHy, y[crl], y[crl - 1], -1);
		x[crl] -= sumx; y[crl] -= sumy;
		upd(sLx, sHx, x[crl], x[crl - 1] - sumx, 1);
		upd(sLy, sHy, y[crl], y[crl - 1] - sumy, 1);
		crl--;
	}
}

void frt() {
	if (crl < n) {
		crl++;
		x[crl] += sumx; y[crl] += sumy;
		upd(pLx, pHx, x[crl], x[crl - 1], 1);
		upd(pLy, pHy, y[crl], y[crl - 1], 1);
		upd(sLx, sHx, x[crl] - sumx, x[crl - 1] - sumx, -1);
		upd(sLy, sHy, y[crl] - sumy, y[crl - 1] - sumy, -1);
	}
}

int main() {
	if (fopen(taskname".inp", "r")) {
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
	else {
		if (fopen(taskname".in", "r")) {
			freopen(taskname".in", "r", stdin);
			freopen(taskname".out", "w", stdout);
		}
	}

	cin.tie(0)->sync_with_stdio(0);

	cin >> n;

	x[0] = y[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
	}

	build(x, pLx, pHx, sLx, sHx);
	build(y, pLy, pHy, sLy, sHy);

	cin >> m;
	crl = 1;
	char c; int X, Y;
	while (m--) {
		cin >> c;
		if (c == 'B') {
			bck();
		}
		else {
			if (c == 'F') {
				frt();
			}
			else {
				if (c == 'C') {
					cin >> X >> Y;
					upd(pLx, pHx, x[crl], x[crl - 1], -1);
					upd(pLy, pHy, y[crl], y[crl - 1], -1);
					if (crl < n) {
						upd(sLx, sHx, x[crl + 1], x[crl] - sumx, -1);
						upd(sLy, sHy, y[crl + 1], y[crl] - sumy, -1);
					}
					sumx += X - x[crl] + x[crl - 1];
					sumy += Y - y[crl] + y[crl - 1];
					x[crl] = x[crl - 1] + X;
					y[crl] = y[crl - 1] + Y;

					upd(pLx, pHx, x[crl], x[crl - 1], 1);
					upd(pLy, pHy, y[crl], y[crl - 1], 1);
					if (crl < n) {
						upd(sLx, sHx, x[crl + 1], x[crl] - sumx, 1);
						upd(sLy, sHy, y[crl + 1], y[crl] - sumy, 1);
					}
				}
				else {
					cout << sLx.get(-sumx) - sHx.get(-sumx) + pLx.get(0) - pHx.get(0) + sLy.get(-sumy) - sHy.get(-sumy) + pLy.get(0) - pHy.get(0) << "\n";
				}
			}
		}
	}

	return 0;
}

Compilation message

ruka.cpp: In function 'void build(int*, BIT&, BIT&, BIT&, BIT&)':
ruka.cpp:45:18: warning: unused variable 'a' [-Wunused-variable]
   45 |  for (int i = 2, a, b; i <= n; i++) {
      |                  ^
ruka.cpp:45:21: warning: unused variable 'b' [-Wunused-variable]
   45 |  for (int i = 2, a, b; i <= n; i++) {
      |                     ^
ruka.cpp: In function 'int main()':
ruka.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    freopen(taskname".in", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    freopen(taskname".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 4 ms 460 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 368 ms 13396 KB Output is correct
6 Correct 341 ms 11416 KB Output is correct
7 Correct 356 ms 9528 KB Output is correct
8 Correct 347 ms 9904 KB Output is correct

Subtask #3
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 368 ms 13396 KB Output is correct
6 Correct 341 ms 11416 KB Output is correct
7 Correct 356 ms 9528 KB Output is correct
8 Correct 347 ms 9904 KB Output is correct
9 Correct 1054 ms 27288 KB Output is correct
10 Correct 1106 ms 30940 KB Output is correct
11 Correct 933 ms 26312 KB Output is correct
12 Correct 923 ms 22692 KB Output is correct