Submission #90736

#	Time	Username	Problem	Language	Result	Execution time	Memory
90736		combi2k2	Cake (CEOI14_cake)	C++14	10 / 100	2062 ms	6420 KiB

cake

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

const int   N   = 1e6 + 1;

typedef pair<int,int>   ii;

int it[N];
int lz[N];

void push(int i,int l,int r)    {
    if (!lz[i]) return;
    it[i] += lz[i];
    if (l < r)  {
        lz[i << 1]     += lz[i];
        lz[i << 1 | 1] += lz[i];
    }
    lz[i] = 0;
}
void _upd(int i,int l,int r,int L,int R,int v)  {
    push(i,l,r);
    if (l > R || r < L) return;
    if (L <= l && r <= R)   {
        lz[i] = v;
        push(i,l,r);
        return;
    }
    int m = (l + r) / 2;
    _upd(i << 1    ,l,m,L,R,v); ++m;
    _upd(i << 1 | 1,m,r,L,R,v);
    it[i] = max(it[i << 1],it[i << 1 | 1]);
}
int _get(int i,int l,int r,int L,int R) {
    push(i,l,r);
    if (l > R || r < L)     return  0;
    if (L <= l && r <= R)   return  it[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 n, a;

ii  getpos1()   {   //find minimum element
    int l = 1, r = n;
    int p = 1;
    while (l < r)   {
        int m = (l + r) / 2;
        p <<= 1;
        push(p,l,m);
        push(p | 1,m + 1,r);
        if (it[p] == it[1])
            r = m;
        else
            l = m + 1,
            p |= 1;
    }
    push(p,l,l);
    return  {l,it[p]};
}

int tot = 1;

void update(int x,int e)    {
    vector<int> v;
    int val = it[1] + N;
    for(int i = 1 ; i < e ; ++i)    {
        ii  p = getpos1();
        v.push_back(p.X);
        val = min(val,p.Y);
        _upd(1,1,n,p.X,p.X,-N);
    }
    for(int p : v)
        _upd(1,1,n,p,p,N);
    _upd(1,1,n,x,x,val - 1 - _get(1,1,n,x,x));
    v.push_back(x);
    v.push_back(0);
    v.push_back(n + 1);
    sort(v.begin(),v.end());
    for(int i = 1 ; i < v.size() ; ++i)
        _upd(1,1,n,v[i - 1] + 1,v[i] - 1,-1);
}

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,i,N + x);
    }

    int q;  cin >> q;

    while (q--) {
        char t;
        int  x;

        cin >> t >> x;

        if (t == 'E')   {
            int y;  cin >> y;
            update(x,y);
        }
        else    {
            if (x == a || a == 1 || a == n) {
                cout << abs(x - a) << "\n";
                continue;
            }
            if (x > a)  {
                int y = _get(1,1,n,a + 1,x);
                if (_get(1,1,n,1,a - 1) < y)    {
                    cout << x - 1 << "\n";
                    continue;
                }
                int L = 1, R = a - 1;
                while (L < R)   {
                    int M = (L + R + 2) / 2;
                    if (_get(1,1,n,M,a - 1) > y)
                        L = M;
                    else
                        R = M - 1;
                }
                cout << x - L - 1 << "\n";
            }
            if (x < a)  {
                int y = _get(1,1,n,x,a - 1);
                if (_get(1,1,n,a + 1,n) < y)    {
                    cout << n - x << "\n";
                    continue;
                }
                int L = a + 1, R = n;
                while (L < R)   {
                    int M = (L + R) / 2;
                    if (_get(1,1,n,a + 1,M) > y)
                        R = M;
                    else
                        L = M + 1;
                }
                cout << L - x - 1 << "\n";
            }
        }
    }
}

Compilation message (stderr)

cake.cpp: In function 'void update(int, int)':
cake.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1 ; i < v.size() ; ++i)
                     ~~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 10 / 20
• Subtask 4: 0 / 50