oj.uz

Submission #25979

# Submission time Handle Problem Language Result Execution time Memory
25979 2017-06-25T09:41:08 Z 카제비(#1091) Cake (CEOI14_cake) C++14
100 / 100
 1259 ms 14948 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 3e5 + 100, MAX_Q = 5e5 + 100;

int N, X, Q, Nr[MAX_N];
vector<int> Ls, Rs;
set<pi> S;
void changeNr(int ix, int v) {
	S.erase(pi(Nr[ix], ix));
	vector<pi> Save;
	for(int i=0; i+1<v; i++) {
		auto it = S.end(); it--;
		pi now = *it; now.one++;
		Save.push_back(now);
		Nr[now.two] = now.one;
		S.erase(it);
	}
	auto it = S.end(); it--;
	pi now = *it;
	Nr[ix] = now.one + 1;
	S.insert(pi(now.one+1, ix));
	for(pi &e : Save) S.insert(e);
}
void setNr(int ix, int v) {
	changeNr(ix, v);
//	for(pi e : S) printf("[%d %d] ", e.one, e.two); puts("");
	if(ix == X) return;
	vector<int> temp;
	if(ix < X) {
		while(!Ls.empty() && Ls.back() <= ix) temp.push_back(Ls.back()), Ls.pop_back();
		if(temp.empty() || temp.back() != ix) temp.push_back(ix);
		for(int i=SZ(temp)-1; i>=0; i--)
			if(Ls.empty() || Nr[Ls.back()] < Nr[temp[i]])
				Ls.push_back(temp[i]);
	} else {
		while(!Rs.empty() && Rs.back() >= ix) temp.push_back(Rs.back()), Rs.pop_back();
		if(temp.empty() || temp.back() != ix) temp.push_back(ix);
		for(int i=SZ(temp)-1; i>=0; i--)
			if(Rs.empty() || Nr[Rs.back()] < Nr[temp[i]])
				Rs.push_back(temp[i]);
	}
//	printf("[Ls Rs]\n"); for(int l : Ls) printf("%d ", l); puts(""); for(int r : Rs) printf("%d ", r); puts("");
}
int getAns(int ix) {
	if(ix == X) return 0;
	int ans = abs(X - ix);
//	printf("ix = %d\n", ix);
	if(ix < X) {
		int l = lower_bound(ALL(Ls), ix-1, [&](int a, int b) {
			return a > b;
		}) - Ls.begin() - 1;

		int r = SZ(Rs);
		for(int a=0, b=SZ(Rs)-1; a<=b; ) {
			int m = (a+b) >> 1;
			if(Nr[Rs[m]] > Nr[Ls[l]]) r = m, b = m-1; else a = m+1;
		}

//		printf("left [%d] | [%d]\n", l, r);

		int rix = N+1;
		if(r < SZ(Rs)) rix = Rs[r];
		ans += abs(rix - X - 1);
	} else {
		int r = lower_bound(ALL(Rs), ix+1) - Rs.begin() - 1;

		int l = SZ(Ls);
		for(int a=0, b=SZ(Ls)-1; a<=b; ) {
			int m = (a+b) >> 1;
			if(Nr[Ls[m]] > Nr[Rs[r]]) l = m, b = m-1; else a = m+1;
		}

//		printf("right [%d] | [%d]\n", r, l);

		int lix = 0;
		if(l < SZ(Ls)) lix = Ls[l];
		ans += abs(X - lix - 1);
	}
	return ans;
}
int main() {
	cin >> N >> X;
	REPO(i, N) scanf("%d", &Nr[i]);
	cin >> Q;
	REPO(i, N) S.insert(pi(Nr[i], i));
	for(int i=X-1; i>=1; i--) 
		if(Ls.empty() || Nr[Ls.back()] < Nr[i]) Ls.push_back(i);
	for(int i=X+1; i<=N; i++)
		if(Rs.empty() || Nr[Rs.back()] < Nr[i]) Rs.push_back(i);

	REP(q, Q) {
		char s[3]; int x, y;
		scanf("%s", s); scanf("%d", &x);
		if(s[0] == 'F') {
			printf("%d\n", getAns(x));
		} else {
			scanf("%d", &y);
			setNr(x, y);
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:96:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REPO(i, N) scanf("%d", &Nr[i]);
                                ^
cake.cpp:106:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s); scanf("%d", &x);
                 ^
cake.cpp:106:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s); scanf("%d", &x);
                                  ^
cake.cpp:110:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3200 KB Output is correct
2 Correct 0 ms 3200 KB Output is correct
3 Correct 0 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 16 ms 3728 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 3596 KB Output is correct
2 Correct 399 ms 3728 KB Output is correct
3 Correct 496 ms 3728 KB Output is correct
4 Correct 256 ms 3728 KB Output is correct
5 Correct 779 ms 4388 KB Output is correct
6 Correct 659 ms 4388 KB Output is correct
7 Correct 599 ms 4388 KB Output is correct
8 Correct 349 ms 4388 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7952 KB Output is correct
2 Correct 86 ms 7952 KB Output is correct
3 Correct 73 ms 7952 KB Output is correct
4 Correct 0 ms 3200 KB Output is correct
5 Correct 323 ms 14948 KB Output is correct
6 Correct 346 ms 14948 KB Output is correct
7 Correct 136 ms 14948 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3332 KB Output is correct
2 Correct 43 ms 3464 KB Output is correct
3 Correct 106 ms 5576 KB Output is correct
4 Correct 139 ms 5576 KB Output is correct
5 Correct 139 ms 3332 KB Output is correct
6 Correct 213 ms 6236 KB Output is correct
7 Correct 193 ms 3728 KB Output is correct
8 Correct 349 ms 7952 KB Output is correct
9 Correct 1259 ms 14948 KB Output is correct
10 Correct 536 ms 3332 KB Output is correct
11 Correct 739 ms 4124 KB Output is correct
12 Correct 1146 ms 12572 KB Output is correct
13 Correct 959 ms 14948 KB Output is correct