oj.uz

Submission #164595

# Submission time Handle Problem Language Result Execution time Memory
164595 2019-11-22T00:47:06 Z arnold518 Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 17900 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];
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: 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]), S.insert({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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 11 ms 376 KB Output is correct
5 Correct 31 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 1476 KB Output is correct
2 Correct 489 ms 1528 KB Output is correct
3 Correct 489 ms 1888 KB Output is correct
4 Correct 246 ms 1528 KB Output is correct
5 Correct 847 ms 2808 KB Output is correct
6 Correct 707 ms 2936 KB Output is correct
7 Correct 560 ms 2424 KB Output is correct
8 Correct 325 ms 2808 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 7672 KB Output is correct
2 Correct 331 ms 7320 KB Output is correct
3 Correct 338 ms 7444 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 598 ms 16648 KB Output is correct
6 Correct 742 ms 16632 KB Output is correct
7 Correct 543 ms 16496 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 1016 KB Output is correct
2 Correct 98 ms 1400 KB Output is correct
3 Correct 248 ms 4500 KB Output is correct
4 Correct 261 ms 4472 KB Output is correct
5 Correct 296 ms 1912 KB Output is correct
6 Correct 489 ms 5560 KB Output is correct
7 Correct 342 ms 2424 KB Output is correct
8 Correct 419 ms 7416 KB Output is correct
9 Execution timed out 2050 ms 17900 KB Time limit exceeded
10 Correct 958 ms 2496 KB Output is correct
11 Correct 1362 ms 3996 KB Output is correct
12 Execution timed out 2077 ms 15224 KB Time limit exceeded
13 Execution timed out 2067 ms 17656 KB Time limit exceeded