oj.uz

Submission #101076

# Submission time Handle Problem Language Result Execution time Memory
101076 2019-03-16T11:56:32 Z Bruteforceman Cake (CEOI14_cake) C++11
0 / 100
 680 ms 8552 KB 
#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9;
const int ts = 250001;
int d[250010];
int n, a;
vector <int> best;
int sz;

struct tree {
	int t[250010 * 4];
	void update(int x, int val, int c = 1, int b = 1, int e = ts) {
		if(b == e) {
			t[c] = val;
			return ;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(x <= m) update(x, val, l, b, m);
		else update(x, val, r, m + 1, e);
		t[c] = max(t[l], t[r]);
	}
	int query(int x, int y, int c = 1, int b = 1, int e = ts) {
		if(x <= b && e <= y) return t[c];
		if(y < b || e < x) return 0;
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		return max(query(x, y, l, b, m), query(x, y, r, m + 1, e));
	}
	int searchSuffix(int val, int c = 1, int b = 1, int e = ts) {
		if(b == e) {
			return t[c] > val ? b : 0;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(t[r] > val) return searchSuffix(val, r, m + 1, e);
		else return searchSuffix(val, l, b, m);
	}
	int searchPrefix(int val, int c = 1, int b = 1, int e = ts) {
		if(b == e) {
			return t[c] > val ? b : n+1;
		}
		int m = (b + e) >> 1;
		int l = c << 1;
		int r = l + 1;
		if(t[l] > val) return searchPrefix(val, l, b, m);
		else return searchPrefix(val, r, m + 1, e);
	}
} P, S;

int query(int b) {
	if(b == a) return 0;
	if(b < a) {
		int mx = P.query(b, a);
		int idx = S.searchPrefix(mx);
		return idx - b - 1;
	} else {
		int mx = S.query(a, b);
		int idx = P.searchSuffix(mx);
		return b - idx - 1;
	}
} 

bool cmp(int p, int q) {
	return d[p] > d[q];
}
void update(int p, int q) {
	if(p == a) return ;
	--q;
	int pos = -1;
	for(int i = 0; i < sz; i++) {
		if(best[i] == p) {
			pos = i;
			break;
		}
	}
	if(pos == -1) {
		d[p] = d[best[q]];
		best.insert(best.begin() + q, p);
		best.pop_back();
		for(int i = 0; i <= q; i++) {
			d[best[i]] += 1;
		}
	} else {
		while(pos < q) {
			swap(d[best[pos]], d[best[pos + 1]]);
			swap(best[pos], best[pos + 1]);
			++pos;
		}
		while(pos > q) {
			swap(d[best[pos]], d[best[pos - 1]]);
			swap(best[pos], best[pos - 1]);
			--pos;
		}
	}
	for(int i = 0; i < sz; i++) {
		// cout << best[i] << " " << d[best[i]] << endl;
		if(best[i] < a) {
			P.update(best[i], d[best[i]]);
		} else {
			S.update(best[i], d[best[i]]);
		}
	}
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &a);
	sz = min(10, n-1);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		if(i != a) {
			best.emplace_back(i);
		}
	}
	sort(best.begin(), best.end(), cmp);
	best.resize(sz);

	for(int i = a + 1; i <= n; i++) {
		S.update(i, d[i]);
	}
	for(int i = 1; i < a; i++) {
		P.update(i, d[i]);
	}
	int q;
	scanf("%d", &q);
	while(q--) {
		char c;
		int p, q;
		scanf(" %c", &c);
		if(c == 'F') {
			scanf("%d", &p);
			printf("%d\n", query(p));
		} else {
			scanf("%d %d", &p, &q);
			update(p, q);
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'int main(int, const char**)':
cake.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &a);
  ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
cake.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
cake.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &p, &q);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 6 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 2864 KB Output is correct
2 Incorrect 342 ms 2936 KB Output isn't correct
3 Correct 328 ms 2936 KB Output is correct
4 Correct 304 ms 2936 KB Output is correct
5 Correct 385 ms 3220 KB Output is correct
6 Incorrect 370 ms 3192 KB Output isn't correct
7 Correct 494 ms 3220 KB Output is correct
8 Correct 380 ms 3220 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 4240 KB Output is correct
2 Incorrect 101 ms 4000 KB Output isn't correct
3 Incorrect 92 ms 3952 KB Output isn't correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 164 ms 7404 KB Output is correct
6 Correct 168 ms 7552 KB Output is correct
7 Incorrect 127 ms 7148 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 1016 KB Output isn't correct
2 Incorrect 42 ms 1024 KB Output isn't correct
3 Incorrect 82 ms 2420 KB Output isn't correct
4 Correct 82 ms 2560 KB Output is correct
5 Incorrect 122 ms 2036 KB Output isn't correct
6 Correct 177 ms 3700 KB Output is correct
7 Correct 204 ms 2680 KB Output is correct
8 Correct 214 ms 4436 KB Output is correct
9 Correct 571 ms 8496 KB Output is correct
10 Incorrect 362 ms 3924 KB Output isn't correct
11 Correct 413 ms 4472 KB Output is correct
12 Correct 680 ms 7660 KB Output is correct
13 Correct 569 ms 8552 KB Output is correct