Submission #71462

#	Time	Username	Problem	Language	Result	Execution time	Memory
71462		kingpig9	Cake (CEOI14_cake)	C++11	100 / 100	514 ms	23196 KiB

cake

#include <bits/stdc++.h>

using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))

const int MAXN = 1 << 18;

void setmax (int &a, int b) {
	if (a < b) {
		a = b;
	}
}

struct fenwick {
	int bit[MAXN];

	int query (int x) {
		int res = 0;
		for (; x; x &= x - 1) {
			setmax(res, bit[x]);
		}
		return res;
	}

	void update (int x, int v) {
		for (; x < MAXN; x += (x & -x)) {
			setmax(bit[x], v);
		}
	}

	int find (int q) {
		//last query that's < q
		int pos = 0;
		for (int i = 17; i >= 0; i--) {
			int npos = pos + (1 << i);
			if (bit[npos] < q) {
				pos = npos;
			}
		}
		return pos;
	}
};

int N, S;
int A[MAXN];
vector<int> top10;
fenwick lfen, rfen;
int curv;

bool cmp10 (int x, int y) {
	return A[x] > A[y];
}

void adjust_top10() {
	sort(all(top10), cmp10);
	top10.resize(min(N, 10));
}

void upda (int x, int v) {
	A[x] = v;
	if (x < S) {
		lfen.update(S - x, v);
	} else if (x > S) {
		rfen.update(x - S, v);
	}
}

int main() {
	scanf("%d %d", &N, &S);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
		upda(i, A[i]);
		top10.push_back(i);
	}

	lfen.update(S, 2e9);
	rfen.update(N - S + 1, 2e9);
	adjust_top10();
	curv = N;

	int nq, x, e;
	char qtype;
	
	for (scanf("%d", &nq); nq--; ) {
		scanf(" %c", &qtype);
		if (qtype == 'E') {
			scanf("%d %d", &x, &e);
			e--;
			auto it = find(all(top10), x);
			if (it != top10.end()) {
				top10.erase(it);
			}

			top10.insert(top10.begin() + e, x);
			for (int i = e; i >= 0; i--) {
				upda(top10[i], ++curv);
			}
			top10.resize(min(N, 10));
			//debug("assert\n");
			adjust_top10();
		} else {
			scanf("%d", &x);
			if (x == S) {
				puts("0");
				continue;
			}

			int cntx = abs(x - S);
			int mx, cnto;
			if (x < S) {
				mx = lfen.query(cntx);
				cnto = rfen.find(mx + 1);
			} else {
				mx = rfen.query(cntx);
				cnto = lfen.find(mx + 1);
			}

			printf("%d\n", cntx + cnto);
		}
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &S);
  ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:90:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (scanf("%d", &nq); nq--; ) {
       ~~~~~^~~~~~~~~~~
cake.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &qtype);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &x, &e);
    ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~

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