oj.uz

Submission #52521

# Submission time Handle Problem Language Result Execution time Memory
52521 2018-06-26T06:31:44 Z zadrga Cake (CEOI14_cake) C++14
100 / 100
 1956 ms 18172 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 3 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 11 ms 552 KB Output is correct
5 Correct 27 ms 1120 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 1180 KB Output is correct
2 Correct 454 ms 1180 KB Output is correct
3 Correct 634 ms 1188 KB Output is correct
4 Correct 316 ms 1312 KB Output is correct
5 Correct 1198 ms 2068 KB Output is correct
6 Correct 883 ms 2128 KB Output is correct
7 Correct 745 ms 2248 KB Output is correct
8 Correct 360 ms 2248 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 7376 KB Output is correct
2 Correct 124 ms 7376 KB Output is correct
3 Correct 114 ms 7376 KB Output is correct
4 Correct 3 ms 7376 KB Output is correct
5 Correct 463 ms 16108 KB Output is correct
6 Correct 417 ms 16108 KB Output is correct
7 Correct 218 ms 16108 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 16108 KB Output is correct
2 Correct 61 ms 16108 KB Output is correct
3 Correct 167 ms 16108 KB Output is correct
4 Correct 229 ms 16108 KB Output is correct
5 Correct 239 ms 16108 KB Output is correct
6 Correct 381 ms 16108 KB Output is correct
7 Correct 243 ms 16108 KB Output is correct
8 Correct 477 ms 16108 KB Output is correct
9 Correct 1956 ms 17180 KB Output is correct
10 Correct 855 ms 17180 KB Output is correct
11 Correct 1195 ms 17180 KB Output is correct
12 Correct 1946 ms 17180 KB Output is correct
13 Correct 1480 ms 18172 KB Output is correct