oj.uz

답안 #164583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
164583 2019-11-21T17:11:43 Z arnold518 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 135208 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);
                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, 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]);

            for(i=1; i<=N; i++) printf("%d ", D[i]);
        }
    }
}

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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 111060 KB Time limit exceeded
2 Execution timed out 2070 ms 116752 KB Time limit exceeded
3 Execution timed out 2074 ms 113380 KB Time limit exceeded
4 Execution timed out 2053 ms 114940 KB Time limit exceeded
5 Execution timed out 2053 ms 117896 KB Time limit exceeded
6 Execution timed out 2051 ms 127332 KB Time limit exceeded
7 Execution timed out 2069 ms 114996 KB Time limit exceeded
8 Execution timed out 2037 ms 121152 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1403 ms 63396 KB Output isn't correct
2 Incorrect 1152 ms 59196 KB Output isn't correct
3 Incorrect 1187 ms 58120 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Execution timed out 2043 ms 113584 KB Time limit exceeded
6 Execution timed out 2033 ms 112532 KB Time limit exceeded
7 Execution timed out 2045 ms 124572 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2016 ms 105680 KB Time limit exceeded
2 Execution timed out 2054 ms 107068 KB Time limit exceeded
3 Execution timed out 2036 ms 123068 KB Time limit exceeded
4 Execution timed out 2043 ms 131140 KB Time limit exceeded
5 Execution timed out 2068 ms 109620 KB Time limit exceeded
6 Execution timed out 2031 ms 117852 KB Time limit exceeded
7 Execution timed out 2040 ms 109116 KB Time limit exceeded
8 Execution timed out 2076 ms 128944 KB Time limit exceeded
9 Execution timed out 2079 ms 135208 KB Time limit exceeded
10 Execution timed out 2064 ms 108456 KB Time limit exceeded
11 Execution timed out 2037 ms 109940 KB Time limit exceeded
12 Execution timed out 2055 ms 130660 KB Time limit exceeded
13 Execution timed out 2058 ms 130564 KB Time limit exceeded