oj.uz

Submission #90736

# Submission time Handle Problem Language Result Execution time Memory
90736 2018-12-24T08:01:17 Z combi2k2 Cake (CEOI14_cake) C++14
10 / 100
 2000 ms 6420 KB 
#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

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.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1184 ms 800 KB Output is correct
2 Correct 579 ms 800 KB Output is correct
3 Correct 762 ms 844 KB Output is correct
4 Incorrect 391 ms 884 KB Output isn't correct
5 Correct 1309 ms 1016 KB Output is correct
6 Correct 970 ms 1020 KB Output is correct
7 Correct 860 ms 1108 KB Output is correct
8 Incorrect 443 ms 1172 KB Output isn't correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 3360 KB Output is correct
2 Correct 229 ms 3360 KB Output is correct
3 Correct 168 ms 3360 KB Output is correct
4 Incorrect 2 ms 3360 KB Output isn't correct
5 Correct 213 ms 5440 KB Output is correct
6 Correct 277 ms 5456 KB Output is correct
7 Correct 269 ms 5456 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 5456 KB Output isn't correct
2 Correct 104 ms 5456 KB Output is correct
3 Correct 251 ms 5456 KB Output is correct
4 Incorrect 267 ms 5456 KB Output isn't correct
5 Incorrect 306 ms 5456 KB Output isn't correct
6 Correct 400 ms 5456 KB Output is correct
7 Correct 355 ms 5456 KB Output is correct
8 Correct 442 ms 5456 KB Output is correct
9 Execution timed out 2040 ms 6324 KB Time limit exceeded
10 Incorrect 992 ms 6324 KB Output isn't correct
11 Correct 1496 ms 6324 KB Output is correct
12 Execution timed out 2062 ms 6420 KB Time limit exceeded
13 Execution timed out 2009 ms 6420 KB Time limit exceeded