oj.uz

Submission #164596

# Submission time Handle Problem Language Result Execution time Memory
164596 2019-11-22T00:51:09 Z arnold518 Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 17144 KB 
#pragma gcc optimize (Ofast)
#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];
set<pii, greater<pii>> S;

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]), S.insert({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--;
            S.erase({D[a], a});
            vector<pii> T;
            auto it=S.begin();
            for(i=0; i<b; i++, it++) T.push_back(*it);
            int val=S.begin()->first+2;
            for(auto it : T)
            {
                S.erase(it);
                D[it.second]++;
                S.insert({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;
            S.insert({D[a], a});
            update(1, 0, N+1, a, D[a]);
        }
    }
}

Compilation message

cake.cpp:1:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize (Ofast)
 
cake.cpp: In function 'void init(int, int, int)':
cake.cpp:24: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:37: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:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:77:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int mid=lo+hi>>1;
                             ~~^~~
cake.cpp:89:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int mid=lo+hi>>1;
                             ~~^~~
cake.cpp:53:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
cake.cpp:55: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:56: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]), S.insert({D[i], i});
                         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &t);
         ~~~~~^~~~~~~~~~~
cake.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:99: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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 11 ms 376 KB Output is correct
4 Correct 11 ms 376 KB Output is correct
5 Correct 30 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 1120 KB Output is correct
2 Correct 406 ms 1144 KB Output is correct
3 Correct 497 ms 1016 KB Output is correct
4 Correct 243 ms 1016 KB Output is correct
5 Correct 868 ms 2040 KB Output is correct
6 Correct 709 ms 2040 KB Output is correct
7 Correct 552 ms 2168 KB Output is correct
8 Correct 318 ms 2064 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 7416 KB Output is correct
2 Correct 331 ms 7356 KB Output is correct
3 Correct 353 ms 7288 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 582 ms 16092 KB Output is correct
6 Correct 755 ms 16144 KB Output is correct
7 Correct 545 ms 15880 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 760 KB Output is correct
2 Correct 103 ms 1016 KB Output is correct
3 Correct 256 ms 3980 KB Output is correct
4 Correct 260 ms 3832 KB Output is correct
5 Correct 284 ms 1048 KB Output is correct
6 Correct 488 ms 5044 KB Output is correct
7 Correct 343 ms 1528 KB Output is correct
8 Correct 366 ms 6520 KB Output is correct
9 Execution timed out 2050 ms 16960 KB Time limit exceeded
10 Correct 975 ms 1804 KB Output is correct
11 Correct 1339 ms 3452 KB Output is correct
12 Execution timed out 2054 ms 14584 KB Time limit exceeded
13 Execution timed out 2063 ms 17144 KB Time limit exceeded