답안 #164656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
164656 2019-11-22T11:15:57 Z arnold518 케이크 (CEOI14_cake) C++14
83.3333 / 100
2000 ms 23416 KB
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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:26: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:39: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:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:79:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int mid=lo+hi>>1;
                             ~~^~~
cake.cpp:91:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     int mid=lo+hi>>1;
                             ~~^~~
cake.cpp:55:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
cake.cpp:57: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:58: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:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &t);
         ~~~~~^~~~~~~~~~~
cake.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &a, &b); b--;
             ~~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 11 ms 504 KB Output is correct
5 Correct 30 ms 1144 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 765 ms 5372 KB Output is correct
2 Correct 380 ms 5496 KB Output is correct
3 Correct 468 ms 5368 KB Output is correct
4 Correct 312 ms 5384 KB Output is correct
5 Correct 832 ms 6520 KB Output is correct
6 Correct 677 ms 7004 KB Output is correct
7 Correct 548 ms 6776 KB Output is correct
8 Correct 313 ms 7160 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 479 ms 8364 KB Output is correct
2 Correct 302 ms 8356 KB Output is correct
3 Correct 315 ms 8312 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 591 ms 18400 KB Output is correct
6 Correct 715 ms 18296 KB Output is correct
7 Correct 503 ms 18088 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 1016 KB Output is correct
2 Correct 95 ms 1364 KB Output is correct
3 Correct 256 ms 4724 KB Output is correct
4 Correct 265 ms 4572 KB Output is correct
5 Correct 275 ms 1960 KB Output is correct
6 Correct 499 ms 6400 KB Output is correct
7 Correct 357 ms 3152 KB Output is correct
8 Correct 353 ms 9080 KB Output is correct
9 Execution timed out 2047 ms 22556 KB Time limit exceeded
10 Correct 908 ms 5320 KB Output is correct
11 Correct 1345 ms 7328 KB Output is correct
12 Execution timed out 2064 ms 19876 KB Time limit exceeded
13 Execution timed out 2065 ms 23416 KB Time limit exceeded