제출 #521815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521815		ntabc05101	Ruka (COI15_ruka)	C++14	100 / 100	1106 ms	30940 KiB

ruka

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56