oj.uz

Submission #71462

# Submission time Handle Problem Language Result Execution time Memory
71462 2018-08-24T18:24:48 Z kingpig9 Cake (CEOI14_cake) C++11
100 / 100
 514 ms 23196 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 7 ms 752 KB Output is correct
5 Correct 12 ms 992 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 5200 KB Output is correct
2 Correct 262 ms 9428 KB Output is correct
3 Correct 244 ms 13760 KB Output is correct
4 Correct 204 ms 13876 KB Output is correct
5 Correct 390 ms 14048 KB Output is correct
6 Correct 303 ms 18784 KB Output is correct
7 Correct 263 ms 18784 KB Output is correct
8 Correct 202 ms 18784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 20220 KB Output is correct
2 Correct 83 ms 20220 KB Output is correct
3 Correct 82 ms 20220 KB Output is correct
4 Correct 2 ms 20220 KB Output is correct
5 Correct 159 ms 21940 KB Output is correct
6 Correct 182 ms 22152 KB Output is correct
7 Correct 159 ms 22152 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22152 KB Output is correct
2 Correct 25 ms 22152 KB Output is correct
3 Correct 53 ms 22152 KB Output is correct
4 Correct 63 ms 22152 KB Output is correct
5 Correct 79 ms 22152 KB Output is correct
6 Correct 114 ms 22152 KB Output is correct
7 Correct 96 ms 22152 KB Output is correct
8 Correct 127 ms 22152 KB Output is correct
9 Correct 450 ms 23132 KB Output is correct
10 Correct 273 ms 23132 KB Output is correct
11 Correct 285 ms 23132 KB Output is correct
12 Correct 514 ms 23132 KB Output is correct
13 Correct 465 ms 23196 KB Output is correct