Submission #90791

#	Time	Username	Problem	Language	Result	Execution time	Memory
90791		combi2k2	Cake (CEOI14_cake)	C++14	100 / 100	482 ms	5544 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50