Submission #164600

#	Time	Username	Problem	Language	Result	Execution time	Memory
164600		arnold518	Cake (CEOI14_cake)	C++14	100 / 100	1761 ms	14696 KiB

cake

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

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