제출 #112532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112532		KCSC	케이크 (CEOI14_cake)	C++14	100 / 100	1583 ms	17048 KiB

cake

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 250005;

int val[NMAX], sgt[NMAX << 2]; 
set<pair<int, int>> mst;

inline bool cmp(int x, int y) {
	return val[x] < val[y]; }

void build(int nod, int lef, int rig) {
	if (lef == rig) {
		sgt[nod] = val[lef]; }
	else {
		int mid = (lef + rig) >> 1;
		build(nod << 1, lef, mid);
		build(nod << 1 | 1, mid + 1, rig);
		sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } }

void update(int nod, int lef, int rig, int ps) {
	if (lef == rig) {
		sgt[nod] = val[ps]; }
	else {
		int mid = (lef + rig) >> 1;
		if (ps <= mid) {
			update(nod << 1, lef, mid, ps); }
		else {
			update(nod << 1 | 1, mid + 1, rig, ps); }		
		sgt[nod] = max(sgt[nod << 1], sgt[nod << 1 | 1]); } }

int query(int nod, int lef, int rig, int st, int en) {
	if (rig < st or en < lef) {
		return -1; }
	if (st <= lef and rig <= en) {
		return sgt[nod]; }
	else {
		int mid = (lef + rig) >> 1;
		return max(query(nod << 1, lef, mid, st, en),
							 query(nod << 1 | 1, mid + 1, rig, st, en)); } }

int binarySearchLeft(int nod, int lef, int rig, int st, int en, int val) {
	if (rig < st or en < lef or sgt[nod] <= val) {
		return -1; }
	else if (lef == rig) {
		return lef; }
	else {
		int mid = (lef + rig) >> 1;
		int ans = binarySearchLeft(nod << 1 | 1, mid + 1, rig, st, en, val);
		if (ans == -1) {
			ans = binarySearchLeft(nod << 1, lef, mid, st, en, val); }
		return ans; } }

int binarySearchRight(int nod, int lef, int rig, int st, int en, int val) {
	if (rig < st or en < lef or sgt[nod] <= val) {
		return -1; }
	else if (lef == rig) {
		return lef; }
	else {
		int mid = (lef + rig) >> 1;
		int ans = binarySearchRight(nod << 1, lef, mid, st, en, val);
		if (ans == -1) {
			ans = binarySearchRight(nod << 1 | 1, mid + 1, rig, st, en, val); } 
		return ans; } } 

int main(void) {
#ifdef HOME
	freopen("cake.in", "r", stdin);
	freopen("cake.out", "w", stdout);
#endif
	int N, P; scanf("%d %d", &N, &P);
	val[0] = val[N + 1] = (int) 1e7;
	for (int i = 1; i <= N; ++i) {
		scanf("%d", &val[i]);
		mst.insert(make_pair(val[i], i)); }
	build(1, 0, N + 1);
	int Q; scanf("%d", &Q);
	while (Q--) {
		char ch; scanf("\n%c ", &ch);
		if (ch == 'E') {
			int pos, kth; scanf("%d %d", &pos, &kth);
			vector<pair<int, int>> axs;
			for (int i = 0; i < kth; ++i) {
				pair<int, int> aux = *mst.rbegin();
				axs.push_back(aux); mst.erase(aux); }
			int axp = -1;
			for (int i = 0; i < kth; ++i) {
				if (axs[i].second == pos) {		
					axp = i; } }
			if (axp != -1) {
				for (; axp + 1 < kth; ++axp) {
					swap(axs[axp + 1].first, axs[axp].first); } 
				for (int i = 0; i < kth; ++i) {
					val[axs[i].second] = axs[i].first;
					mst.insert(axs[i]); 
					update(1, 0, N + 1, axs[i].second); } }
			else {
				mst.erase(make_pair(val[pos], pos));
				val[pos] = axs[kth - 1].first + 1;
				mst.insert(make_pair(val[pos], pos));
				update(1, 0, N + 1, pos);
				for (int i = 0; i + 1 < kth; ++i) {
					val[axs[i].second] = ++axs[i].first;
					mst.insert(axs[i]);
					update(1, 0, N + 1, axs[i].second); } 
				mst.insert(axs[kth - 1]); } } 
		else {
			int pos; scanf("%d", &pos);
			if (pos == P) {
				printf("0\n"); }
			else if (pos < P) {
				printf("%d\n", binarySearchRight(1, 0, N + 1, P + 1, N + 1, query(1, 0, N + 1, pos, P - 1)) - pos - 1); }
			else {
				printf("%d\n", pos - binarySearchLeft(1, 0, N + 1, 0, P - 1, query(1, 0, N + 1, P + 1, pos)) - 1); } } } 
	return 0; }

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

cake.cpp: In function 'int main()':
cake.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, P; scanf("%d %d", &N, &P);
            ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &val[i]);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d", &Q);
         ~~~~~^~~~~~~~~~
cake.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char ch; scanf("\n%c ", &ch);
            ~~~~~^~~~~~~~~~~~~~
cake.cpp:81:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int pos, kth; scanf("%d %d", &pos, &kth);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int pos; scanf("%d", &pos);
             ~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50