oj.uz

Submission #90791

# Submission time Handle Problem Language Result Execution time Memory
90791 2018-12-24T12:36:05 Z combi2k2 Cake (CEOI14_cake) C++14
100 / 100
 482 ms 5544 KB 
#include<bits/stdc++.h>

using namespace std;

const int   N   = 3e5 + 1;

int n, a, d[N];
int t[N << 2];
int pos[N];

void _upd(int i,int l,int r,int p,int v)    {
	if (l > p || r < p) return;
	if (l == r) {
		t[i] = v;
		return;
	}
	int m = (l + r) / 2;
	_upd(i << 1    ,l,m,p,v);   ++m;
	_upd(i << 1 | 1,m,r,p,v);
	t[i] = max(t[i << 1],t[i << 1 | 1]);
}
int _get(int i,int l,int r,int L,int R) {
	if (l > R || r < L)     return -1;
	if (L <= l && r <= R)   return  t[i];
	int m = (l + r) / 2;
	return max(_get(i << 1,l,m,L,R),_get(i << 1 | 1,m + 1,r,L,R));
}

int _rig(int i,int l,int r,int p,int v) {
	if (r < p || t[i] < v)  return  -1;
	if (l == r) return  l;
	int m = (l + r) / 2;
	int res = _rig(i << 1    ,l,m,p,v); ++m;
	if (res < 0)
		res = _rig(i << 1 | 1,m,r,p,v);
	return  res;
}
int _lef(int i,int l,int r,int p,int v) {
	if (l > p || t[i] < v)  return  -1;
	if (l == r) return  l;
	int m = (l + r + 2) / 2;
	int res = _lef(i << 1 | 1,m,r,p,v); --m;
	if (res < 0)
		res = _lef(i << 1    ,l,m,p,v);
	return  res;
}
 
int main()  {
    ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> a;
	
	for(int i = 1 ; i <= n ; ++i)   {
		int x;  cin >> x;
		_upd(1,1,n,i,x);
		pos[n - x + 1] = i;
	}
    
    int tot = n;
    
    int q;  cin >> q;
    
    while (q--) {
    	char t;
    	int  x;
    	cin >> t >> x;
    	
    	if (t == 'E')   {
    		int y;  cin >> y;
    		int p = 10;
    		for(int i = 1 ; i <= 10 ; ++i)
    			if (pos[i] == x)    p = i;
    		for(int i = p ; i > y ; --i)
    			pos[i] = pos[i - 1];
    		pos[y] = x;
    		for(int i = y ; i ; --i)
    			_upd(1,1,n,pos[i],++tot);
		}
		else    {
			if (x == a) {
				cout << "0\n";
				continue;
			}
            int res;
            if (x < a)  {
            	res = _rig(1,1,n,a + 1,_get(1,1,n,x,a - 1));
            	if (res < 0)    res = n;
            	else            res--;
			}
			if (x > a)  {
				res = _lef(1,1,n,a - 1,_get(1,1,n,a + 1,x));
				if (res < 0)    res = 1;
				else            res++;
			}
			cout << abs(res - x) << "\n";
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:96:20: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
    cout << abs(res - x) << "\n";
                ~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 4 ms 484 KB Output is correct
5 Correct 10 ms 740 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 752 KB Output is correct
2 Correct 161 ms 1044 KB Output is correct
3 Correct 184 ms 1044 KB Output is correct
4 Correct 118 ms 1044 KB Output is correct
5 Correct 278 ms 1132 KB Output is correct
6 Correct 237 ms 1132 KB Output is correct
7 Correct 206 ms 1132 KB Output is correct
8 Correct 128 ms 1132 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2668 KB Output is correct
2 Correct 67 ms 2668 KB Output is correct
3 Correct 60 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 123 ms 4504 KB Output is correct
6 Correct 120 ms 4504 KB Output is correct
7 Correct 94 ms 4504 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4504 KB Output is correct
2 Correct 24 ms 4504 KB Output is correct
3 Correct 53 ms 4504 KB Output is correct
4 Correct 62 ms 4504 KB Output is correct
5 Correct 79 ms 4504 KB Output is correct
6 Correct 91 ms 4504 KB Output is correct
7 Correct 87 ms 4504 KB Output is correct
8 Correct 114 ms 4504 KB Output is correct
9 Correct 460 ms 5544 KB Output is correct
10 Correct 260 ms 5544 KB Output is correct
11 Correct 329 ms 5544 KB Output is correct
12 Correct 482 ms 5544 KB Output is correct
13 Correct 413 ms 5544 KB Output is correct