oj.uz

Submission #101088

# Submission time Handle Problem Language Result Execution time Memory
101088 2019-03-16T12:47:50 Z Bruteforceman Cake (CEOI14_cake) C++11
100 / 100
 703 ms 6344 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) {
	--q;
	int pos = find(best.begin(), best.end(), p) - best.begin();
	if(pos < best.size()) {
		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;
		}
	} else {
		int opt = d[best.front()];
		best.insert(best.begin() + q, p);
		best.pop_back();
		opt += 20;
		for(int i = 0; i < best.size(); i++) {
			d[best[i]] = opt - i;
		}
	}
	for(int i = 0; i < best.size(); i++) {
		if(best[i] == a) continue;
		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);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		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 'void update(int, int)':
cake.cpp:73:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(pos < best.size()) {
     ~~~~^~~~~~~~~~~~~
cake.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < best.size(); i++) {
                  ~~^~~~~~~~~~~~~
cake.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < best.size(); i++) {
                 ~~^~~~~~~~~~~~~
cake.cpp: In function 'int main(int, const char**)':
cake.cpp:105: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:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &c);
   ~~~~~^~~~~~~~~~~
cake.cpp:127:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
cake.cpp:130: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
15.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 3 ms 384 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 13 ms 704 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 760 KB Output is correct
2 Correct 343 ms 768 KB Output is correct
3 Correct 470 ms 640 KB Output is correct
4 Correct 410 ms 640 KB Output is correct
5 Correct 406 ms 916 KB Output is correct
6 Correct 396 ms 916 KB Output is correct
7 Correct 515 ms 996 KB Output is correct
8 Correct 337 ms 1044 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2672 KB Output is correct
2 Correct 106 ms 2608 KB Output is correct
3 Correct 102 ms 2592 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 160 ms 5340 KB Output is correct
6 Correct 191 ms 5356 KB Output is correct
7 Correct 142 ms 4972 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 576 KB Output is correct
2 Correct 38 ms 632 KB Output is correct
3 Correct 88 ms 1648 KB Output is correct
4 Correct 90 ms 1520 KB Output is correct
5 Correct 139 ms 824 KB Output is correct
6 Correct 171 ms 2116 KB Output is correct
7 Correct 173 ms 1116 KB Output is correct
8 Correct 342 ms 2160 KB Output is correct
9 Correct 703 ms 6316 KB Output is correct
10 Correct 370 ms 1656 KB Output is correct
11 Correct 436 ms 2352 KB Output is correct
12 Correct 600 ms 5492 KB Output is correct
13 Correct 527 ms 6344 KB Output is correct