Submission #25981

#	Time	Username	Problem	Language	Result	Execution time	Memory
25981		kajebiii	Cake (CEOI14_cake)	C++14	100 / 100	1366 ms	14948 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50