oj.uz

Submission #52518

# Submission time Handle Problem Language Result Execution time Memory
52518 2018-06-26T06:29:23 Z zadrga Cake (CEOI14_cake) C++14
100 / 100
 1948 ms 18080 KB 
//8.20
#include <bits/stdc++.h>
  
using namespace std;
  
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define INF (2e9)
#define maxn 250111
 
typedef long long ll;
typedef pair<int, int> pii;

set<pii> s;
int val[maxn], seg[4 * maxn];
int n, a;

struct segtree_right{
	int seg[4 * maxn];

	void update(int x, int l, int d, int i, int y){
		if(l > d || l > i || d < i)
			return;

		if(l == d && l == i){
			seg[x] = y;
			return;
		}

		int mid = (l + d) / 2;
		update(2 * x, l, mid, i, y);
		update(2 * x + 1, mid + 1, d, i, y);
		seg[x] = max(seg[2 * x], seg[2 * x + 1]);
	}

	int find_max(int x, int l, int d, int i, int j){
		if(l > d || l > j || d < i)
			return -1;

		if(i <= l && d <= j)
			return seg[x];

		int mid = (l + d) / 2;
		int ret = find_max(2 * x, l, mid, i, j);
		ret = max(ret, find_max(2 * x + 1, mid + 1, d, i, j));
		return ret;
	}

	int query(int x, int l, int d, int y){
		if(l > d)
			return -1;

		if(l == d){
			if(seg[x] <= y)
				return d + 1;
			else 
				return d;
		}

		int mid = (l + d) / 2;
		if(seg[2 * x] <= y)
			return query(2 * x + 1, mid + 1, d, y);
		
		if(seg[2 * x] > y)
			return query(2 * x, l, mid, y);
	}
} seg_right;

struct segtree_left{
	int seg[4 * maxn];

	void update(int x, int l, int d, int i, int y){
		if(l > d || l > i || d < i)
			return;

		if(l == d && l == i){
			seg[x] = y;
			return;
		}

		int mid = (l + d) / 2;
		update(2 * x, l, mid, i, y);
		update(2 * x + 1, mid + 1, d, i, y);
		seg[x] = max(seg[2 * x], seg[2 * x + 1]);
	}

	int find_max(int x, int l, int d, int i, int j){
		if(l > d || l > j || d < i)
			return -1;

		if(i <= l && d <= j)
			return seg[x];

		int mid = (l + d) / 2;
		int ret = find_max(2 * x, l, mid, i, j);
		ret = max(ret, find_max(2 * x + 1, mid + 1, d, i, j));
		return ret;
	}

	int query(int x, int l, int d, int y){
		if(l > d)
			return -1;

		if(l == d){
			if(seg[x] <= y)
				return d - 1;
			else 
				return d;
		}

		int mid = (l + d) / 2;
		if(seg[2 * x + 1] <= y)
			return query(2 * x, l, mid, y);
		
		if(seg[2 * x + 1] > y)
			return query(2 * x + 1, mid + 1, d, y);
	}
} seg_left;

int find_ans(int x){
	if(x < a){
		int maks = seg_left.find_max(1, 1, a - 1, x, a - 1);
		int pos = seg_right.query(1, a + 1, n, maks);
		int ret = pos - a + (a - x) - 1;
		return ret;
	}

	if(x > a){
		int maks = seg_right.find_max(1, a + 1, n, a + 1, x);
		int pos = seg_left.query(1, 1, a - 1, maks);
		int ret = a - pos + (x - a) - 1;
		return ret;
	}
}

void change(int x, int y){
	s.erase(mp(val[x], x));
	val[x] = y;
	s.insert(mp(val[x], x));
	if(x < a)
		seg_left.update(1, 1, a - 1, x, val[x]);

	if(x > a)
		seg_right.update(1, a + 1, n, x, val[x]);
}

int main(){
	scanf("%d%d", &n, &a);
	for(int i = 1; i <= n; i++){
		scanf("%d", val + i);
		s.insert(mp(val[i], i));
		if(i < a)
			seg_left.update(1, 1, a - 1, i, val[i]);

		if(i > a)
			seg_right.update(1, a + 1, n, i, val[i]);
	}

	int q;
	scanf("%d", &q);
	while(q--){
		char t[2];
		int x, y;
		scanf("%s%d", t, &x);
		
		if(t[0] == 'F'){
			if(x == a){
				printf("0\n");
				continue;
			}

			printf("%d\n", find_ans(x));
		}

		if(t[0] == 'E'){
			scanf("%d", &y);
			
			auto it = s.end();
			vector<int> cur;
			for(int i = 0; i < y - 1; i++){
				it--;
				cur.pb(it -> se);
			}
			it--;

			change(x, val[it -> se] + 1);

			for(int i : cur)
				change(i, val[i] + 1);
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'int find_ans(int)':
cake.cpp:136:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
cake.cpp: In member function 'int segtree_right::query(int, int, int, int)':
cake.cpp:68:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^
cake.cpp: In member function 'int segtree_left::query(int, int, int, int)':
cake.cpp:119:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^
cake.cpp: In function 'int main()':
cake.cpp:150: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:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", val + i);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d", t, &x);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:178:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
    ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 3 ms 456 KB Output is correct
4 Correct 10 ms 660 KB Output is correct
5 Correct 25 ms 1208 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 1208 KB Output is correct
2 Correct 418 ms 1396 KB Output is correct
3 Correct 608 ms 1396 KB Output is correct
4 Correct 395 ms 1396 KB Output is correct
5 Correct 1067 ms 2152 KB Output is correct
6 Correct 821 ms 2172 KB Output is correct
7 Correct 688 ms 2292 KB Output is correct
8 Correct 377 ms 2300 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 7376 KB Output is correct
2 Correct 127 ms 7376 KB Output is correct
3 Correct 120 ms 7376 KB Output is correct
4 Correct 2 ms 7376 KB Output is correct
5 Correct 398 ms 16140 KB Output is correct
6 Correct 354 ms 16188 KB Output is correct
7 Correct 208 ms 16188 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16188 KB Output is correct
2 Correct 55 ms 16188 KB Output is correct
3 Correct 152 ms 16188 KB Output is correct
4 Correct 204 ms 16188 KB Output is correct
5 Correct 238 ms 16188 KB Output is correct
6 Correct 315 ms 16188 KB Output is correct
7 Correct 272 ms 16188 KB Output is correct
8 Correct 499 ms 16188 KB Output is correct
9 Correct 1948 ms 17144 KB Output is correct
10 Correct 794 ms 17144 KB Output is correct
11 Correct 1057 ms 17144 KB Output is correct
12 Correct 1773 ms 17144 KB Output is correct
13 Correct 1252 ms 18080 KB Output is correct