oj.uz

답안 #112532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
112532 2019-05-20T12:39:01 Z KCSC 케이크 (CEOI14_cake) C++14
100 / 100
 1583 ms 17048 KB 
#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; }

Compilation message

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 21 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 736 ms 988 KB Output is correct
2 Correct 448 ms 1020 KB Output is correct
3 Correct 530 ms 896 KB Output is correct
4 Correct 316 ms 1024 KB Output is correct
5 Correct 881 ms 1876 KB Output is correct
6 Correct 753 ms 1920 KB Output is correct
7 Correct 615 ms 1920 KB Output is correct
8 Correct 417 ms 1920 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 7100 KB Output is correct
2 Correct 98 ms 6976 KB Output is correct
3 Correct 89 ms 6904 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 345 ms 15864 KB Output is correct
6 Correct 334 ms 15888 KB Output is correct
7 Correct 152 ms 15568 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 632 KB Output is correct
2 Correct 50 ms 768 KB Output is correct
3 Correct 140 ms 3632 KB Output is correct
4 Correct 170 ms 3732 KB Output is correct
5 Correct 197 ms 760 KB Output is correct
6 Correct 256 ms 4756 KB Output is correct
7 Correct 206 ms 1568 KB Output is correct
8 Correct 400 ms 6520 KB Output is correct
9 Correct 1583 ms 16872 KB Output is correct
10 Correct 629 ms 1664 KB Output is correct
11 Correct 863 ms 3024 KB Output is correct
12 Correct 1539 ms 14324 KB Output is correct
13 Correct 1138 ms 17048 KB Output is correct