oj.uz

Submission #90787

# Submission time Handle Problem Language Result Execution time Memory
90787 2018-12-24T12:32:58 Z combi2k2 Cake (CEOI14_cake) C++14
0 / 100
 490 ms 5444 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;
    		for(int i = 10 ; 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:93:20: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
    cout << abs(res - x) << "\n";
                ~~~~^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 584 KB Output isn't correct
2 Correct 163 ms 712 KB Output is correct
3 Correct 181 ms 712 KB Output is correct
4 Correct 119 ms 712 KB Output is correct
5 Incorrect 272 ms 924 KB Output isn't correct
6 Correct 242 ms 924 KB Output is correct
7 Correct 203 ms 924 KB Output is correct
8 Correct 126 ms 924 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2584 KB Output is correct
2 Correct 66 ms 2584 KB Output is correct
3 Correct 60 ms 2584 KB Output is correct
4 Incorrect 2 ms 2584 KB Output isn't correct
5 Correct 124 ms 4380 KB Output is correct
6 Incorrect 125 ms 4380 KB Output isn't correct
7 Correct 95 ms 4380 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 4380 KB Output isn't correct
2 Correct 24 ms 4380 KB Output is correct
3 Correct 52 ms 4380 KB Output is correct
4 Correct 65 ms 4380 KB Output is correct
5 Incorrect 80 ms 4380 KB Output isn't correct
6 Correct 96 ms 4380 KB Output is correct
7 Correct 90 ms 4380 KB Output is correct
8 Correct 112 ms 4380 KB Output is correct
9 Incorrect 490 ms 5412 KB Output isn't correct
10 Incorrect 256 ms 5412 KB Output isn't correct
11 Correct 325 ms 5412 KB Output is correct
12 Correct 480 ms 5412 KB Output is correct
13 Incorrect 409 ms 5444 KB Output isn't correct