oj.uz

Submission #52520

# Submission time Handle Problem Language Result Execution time Memory
52520 2018-06-26T06:31:12 Z zadrga Cake (CEOI14_cake) C++14
100 / 100
 1993 ms 18200 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 376 KB Output is correct
3 Correct 4 ms 436 KB Output is correct
4 Correct 12 ms 712 KB Output is correct
5 Correct 28 ms 1148 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 1148 KB Output is correct
2 Correct 443 ms 1180 KB Output is correct
3 Correct 626 ms 1244 KB Output is correct
4 Correct 382 ms 1360 KB Output is correct
5 Correct 1058 ms 2172 KB Output is correct
6 Correct 802 ms 2172 KB Output is correct
7 Correct 737 ms 2176 KB Output is correct
8 Correct 381 ms 2300 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 7312 KB Output is correct
2 Correct 154 ms 7312 KB Output is correct
3 Correct 113 ms 7312 KB Output is correct
4 Correct 3 ms 7312 KB Output is correct
5 Correct 406 ms 16044 KB Output is correct
6 Correct 446 ms 16044 KB Output is correct
7 Correct 218 ms 16044 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 16044 KB Output is correct
2 Correct 55 ms 16044 KB Output is correct
3 Correct 164 ms 16044 KB Output is correct
4 Correct 243 ms 16044 KB Output is correct
5 Correct 264 ms 16044 KB Output is correct
6 Correct 305 ms 16044 KB Output is correct
7 Correct 236 ms 16044 KB Output is correct
8 Correct 506 ms 16044 KB Output is correct
9 Correct 1993 ms 17064 KB Output is correct
10 Correct 868 ms 17064 KB Output is correct
11 Correct 1159 ms 17064 KB Output is correct
12 Correct 1854 ms 17064 KB Output is correct
13 Correct 1411 ms 18200 KB Output is correct