oj.uz

Submission #25981

# Submission time Handle Problem Language Result Execution time Memory
25981 2017-06-25T09:44:19 Z kajebiii Cake (CEOI14_cake) C++14
100 / 100
 1366 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);
	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]);
	}
}
int getAns(int ix) {
	if(ix == X) return 0;
	int ans = abs(X - 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;
		}

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

		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:90: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:100: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:100: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:104: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 3 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 613 ms 3596 KB Output is correct
2 Correct 353 ms 3728 KB Output is correct
3 Correct 466 ms 3728 KB Output is correct
4 Correct 333 ms 3728 KB Output is correct
5 Correct 716 ms 4388 KB Output is correct
6 Correct 669 ms 4388 KB Output is correct
7 Correct 616 ms 4388 KB Output is correct
8 Correct 396 ms 4388 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7952 KB Output is correct
2 Correct 59 ms 7952 KB Output is correct
3 Correct 83 ms 7952 KB Output is correct
4 Correct 0 ms 3200 KB Output is correct
5 Correct 319 ms 14948 KB Output is correct
6 Correct 399 ms 14948 KB Output is correct
7 Correct 143 ms 14948 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3332 KB Output is correct
2 Correct 36 ms 3464 KB Output is correct
3 Correct 93 ms 5576 KB Output is correct
4 Correct 143 ms 5576 KB Output is correct
5 Correct 153 ms 3332 KB Output is correct
6 Correct 233 ms 6236 KB Output is correct
7 Correct 189 ms 3728 KB Output is correct
8 Correct 363 ms 7952 KB Output is correct
9 Correct 1086 ms 14948 KB Output is correct
10 Correct 533 ms 3332 KB Output is correct
11 Correct 759 ms 4124 KB Output is correct
12 Correct 1366 ms 12572 KB Output is correct
13 Correct 943 ms 14948 KB Output is correct