oj.uz

Submission #101073

# Submission time Handle Problem Language Result Execution time Memory
101073 2019-03-16T11:04:02 Z Bruteforceman Cake (CEOI14_cake) C++11
0 / 100
 685 ms 11512 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 && n - sz < d[i]) {
			best.emplace_back(i);
		}
	}
	sort(best.begin(), best.end(), cmp);

	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:110: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:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
cake.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
cake.cpp:136: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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 7 ms 576 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 464 ms 4920 KB Output is correct
2 Incorrect 431 ms 5000 KB Output isn't correct
3 Correct 434 ms 5128 KB Output is correct
4 Correct 410 ms 5104 KB Output is correct
5 Correct 466 ms 5640 KB Output is correct
6 Incorrect 463 ms 5768 KB Output isn't correct
7 Correct 465 ms 5728 KB Output is correct
8 Correct 343 ms 6008 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 3576 KB Output is correct
2 Incorrect 81 ms 3532 KB Output isn't correct
3 Incorrect 97 ms 3448 KB Output isn't correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 166 ms 6520 KB Output is correct
6 Correct 124 ms 6520 KB Output is correct
7 Incorrect 112 ms 6260 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 948 KB Output isn't correct
2 Incorrect 42 ms 1024 KB Output isn't correct
3 Incorrect 92 ms 2140 KB Output isn't correct
4 Correct 93 ms 2184 KB Output is correct
5 Incorrect 111 ms 1932 KB Output isn't correct
6 Correct 170 ms 3548 KB Output is correct
7 Correct 166 ms 2652 KB Output is correct
8 Correct 205 ms 4268 KB Output is correct
9 Correct 685 ms 11456 KB Output is correct
10 Incorrect 412 ms 5240 KB Output isn't correct
11 Correct 371 ms 6332 KB Output is correct
12 Correct 639 ms 10492 KB Output is correct
13 Correct 457 ms 11512 KB Output is correct