oj.uz

Submission #52523

# Submission time Handle Problem Language Result Execution time Memory
52523 2018-06-26T06:33:18 Z zadrga Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 18064 KB 
#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:135: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:67: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:118:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^
cake.cpp: In function 'int main()':
cake.cpp:149: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:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", val + i);
   ~~~~~^~~~~~~~~~~~~~~
cake.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:165: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:177: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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 540 KB Output is correct
4 Correct 10 ms 680 KB Output is correct
5 Correct 27 ms 1192 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 1192 KB Output is correct
2 Correct 453 ms 1208 KB Output is correct
3 Correct 599 ms 1380 KB Output is correct
4 Correct 284 ms 1380 KB Output is correct
5 Correct 1097 ms 2164 KB Output is correct
6 Correct 829 ms 2176 KB Output is correct
7 Correct 759 ms 2176 KB Output is correct
8 Correct 415 ms 2184 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 7360 KB Output is correct
2 Correct 124 ms 7360 KB Output is correct
3 Correct 115 ms 7360 KB Output is correct
4 Correct 2 ms 7360 KB Output is correct
5 Correct 424 ms 16136 KB Output is correct
6 Correct 403 ms 16140 KB Output is correct
7 Correct 255 ms 16140 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 16140 KB Output is correct
2 Correct 62 ms 16140 KB Output is correct
3 Correct 182 ms 16140 KB Output is correct
4 Correct 229 ms 16140 KB Output is correct
5 Correct 241 ms 16140 KB Output is correct
6 Correct 331 ms 16140 KB Output is correct
7 Correct 243 ms 16140 KB Output is correct
8 Correct 474 ms 16140 KB Output is correct
9 Execution timed out 2049 ms 17048 KB Time limit exceeded
10 Correct 919 ms 17048 KB Output is correct
11 Correct 1198 ms 17048 KB Output is correct
12 Correct 1988 ms 17048 KB Output is correct
13 Correct 1362 ms 18064 KB Output is correct