oj.uz

Submission #164600

# Submission time Handle Problem Language Result Execution time Memory
164600 2019-11-22T04:27:10 Z arnold518 Cake (CEOI14_cake) C++14
100 / 100
 1761 ms 14696 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 250000;
const int MAXQ = 500000;

int N, Q, A, D[MAXN+10];
priority_queue<pii> S1, S2;

int tree[4*MAXN+10];

void init(int node, int tl, int tr)
{
    if(tl==tr)
    {
        tree[node]=D[tl];
        return;
    }
    int mid=tl+tr>>1;
    init(node*2, tl, mid);
    init(node*2+1, mid+1, tr);
    tree[node]=max(tree[node*2], tree[node*2+1]);
}

void update(int node, int tl, int tr, int pos, int val)
{
    if(tl==tr)
    {
        tree[node]=val;
        return;
    }
    int mid=tl+tr>>1;
    if(pos<=mid) update(node*2, tl, mid, pos, val);
    else update(node*2+1, mid+1, tr, pos, val);
    tree[node]=max(tree[node*2], tree[node*2+1]);
}

int query(int node, int tl, int tr, int l, int r)
{
    if(l<=tl && tr<=r) return tree[node];
    if(r<tl || tr<l) return 0;
    int mid=tl+tr>>1;
    return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &A);
    for(i=1; i<=N; i++) scanf("%d", &D[i]), S1.push({D[i], i});
    D[0]=D[N+1]=987654321;

    init(1, 0, N+1);

    scanf("%d", &Q);
    while(Q--)
    {
        char t;
        scanf(" %c", &t);
        if(t=='F')
        {
            int x;
            scanf("%d", &x);
            if(x==A) printf("0\n");
            else if(x<A)
            {
                int lo=A, hi=N+1;
                int val=query(1, 0, N+1, x, A-1);
                while(lo+1<hi)
                {
                    int mid=lo+hi>>1;
                    if(query(1, 0, N+1, A+1, mid)>val) hi=mid;
                    else lo=mid;
                }
                printf("%d\n", hi-x-1);
            }
            else
            {
                int lo=0, hi=A;
                int val=query(1, 0, N+1, A+1, x);
                while(lo+1<hi)
                {
                    int mid=lo+hi>>1;
                    if(query(1, 0, N+1, mid, A-1)>val) lo=mid;
                    else hi=mid;
                }
                printf("%d\n", x-lo-1);
            }
        }
        else
        {
            int a, b;
            scanf("%d%d", &a, &b); b--;
            S2.push({D[a], a});
            vector<pii> T;
            int val=S1.top().first+2;
            for(i=0; i<b; i++)
            {
                while(S1.top()==S2.top()) S1.pop(), S2.pop();
                T.push_back(S1.top()); S1.pop();
            }
            for(auto it : T)
            {
                D[it.second]++;
                S1.push({D[it.second], it.second});
                update(1, 0, N+1, it.second, D[it.second]);
                val=min(val, D[it.second]);
            }
            val--;
            D[a]=val;
            S1.push({D[a], a});
            update(1, 0, N+1, a, D[a]);
        }
    }
}

Compilation message

cake.cpp: In function 'void init(int, int, int)':
cake.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
cake.cpp: In function 'void update(int, int, int, int, int)':
cake.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
cake.cpp: In function 'int query(int, int, int, int, int)':
cake.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:76:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int mid=lo+hi>>1;
                             ~~^~~
cake.cpp:88:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int mid=lo+hi>>1;
                             ~~^~~
cake.cpp:52:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
cake.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &A);
     ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:55:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &D[i]), S1.push({D[i], i});
                         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &t);
         ~~~~~^~~~~~~~~~~
cake.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &a, &b); b--;
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 3 ms 248 KB Output is correct
4 Correct 9 ms 504 KB Output is correct
5 Correct 23 ms 888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 5036 KB Output is correct
2 Correct 375 ms 9160 KB Output is correct
3 Correct 423 ms 8712 KB Output is correct
4 Correct 220 ms 8900 KB Output is correct
5 Correct 647 ms 7476 KB Output is correct
6 Correct 572 ms 4780 KB Output is correct
7 Correct 448 ms 13128 KB Output is correct
8 Correct 233 ms 13644 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 3896 KB Output is correct
2 Correct 312 ms 3448 KB Output is correct
3 Correct 324 ms 3364 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 429 ms 6476 KB Output is correct
6 Correct 544 ms 6344 KB Output is correct
7 Correct 473 ms 6248 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 1448 KB Output is correct
2 Correct 83 ms 1196 KB Output is correct
3 Correct 196 ms 3296 KB Output is correct
4 Correct 196 ms 3336 KB Output is correct
5 Correct 236 ms 2772 KB Output is correct
6 Correct 388 ms 5496 KB Output is correct
7 Correct 299 ms 3836 KB Output is correct
8 Correct 228 ms 8416 KB Output is correct
9 Correct 1650 ms 14696 KB Output is correct
10 Correct 790 ms 6956 KB Output is correct
11 Correct 1117 ms 9484 KB Output is correct
12 Correct 1761 ms 13740 KB Output is correct
13 Correct 1746 ms 13280 KB Output is correct