oj.uz

Submission #251018

# Submission time Handle Problem Language Result Execution time Memory
251018 2020-07-20T00:10:15 Z Amine Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 28080 KB 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define f first
#define s second
typedef long long ll;
typedef unsigned long long ull;

void IO(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("test.txt","r",stdin);
    #endif
}

const int N=2e6+3,M=5e3+5,mod=1e9+7,dx[]={1,-1,0,0},
                                    dy[]={0,0,1,-1};
const double eps=1e-9;

int n,m,k,tc,a[N],A,q;

char c;

map<int,int> pos;

set<int> s;

int st[N];

void build(int idx = 1, int l = 0, int r = n - 1){
    if (l == r){
        st[idx] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(idx << 1, l, mid);
    build((idx << 1) + 1,mid + 1, r);
    st[idx] = max(st[idx << 1], st[(idx << 1) + 1]);
}

void update(int idx, int l, int r, int p, int val){
    if (l == r){
        s.erase(a[l]);
        s.insert(val);
        a[l] = val;
        pos.erase(val);
        pos[a[l]] = l;
        st[idx] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    if (l <= p && p <= mid)
        update(idx << 1, l, mid, p, val);
    else
        update((idx << 1) + 1, mid + 1, r, p, val);
    st[idx] = max(st[idx << 1], st[(idx << 1) + 1]);
}

int query(int idx, int l, int r, int ql, int qr){
    if (l >= ql && r <= qr)
        return st[idx];
    if (r < ql || l > qr)
        return 0;
    int mid = (l + r) / 2;
    int ret = query(idx << 1, l, mid, ql, qr);
    ret = max(ret, query((idx << 1) + 1, mid + 1, r, ql, qr));
    return ret;
}

int bs(int l, int r, int x, bool rSide){
    int ret = rSide ? n - 1 : 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if (rSide){
            int mx = query(1, 0, n - 1, l, mid);
            if (mx >= x)
                r = mid - 1, ret = mid - 1;
            else
                l = mid + 1;
        }
        else{
            int mx = query(1, 0, n - 1, mid, r);
            if (mx >= x)
                l = mid + 1, ret = mid + 1;
            else
                r = mid - 1;
        }
    }
    return ret;
}

int main(){
    scanf("%d%d",&n,&A);
    A--;
    for(int i = 0 ; i < n ; i++){
        scanf("%d",&a[i]);
        s.insert(a[i]);
        pos[a[i]] = i;
        if (sz(s) > 10)
            s.erase(s.begin());
    }
    build();
    scanf("%d",&q);
    while(q--){
        scanf(" %c",&c);
        int b,i,e;
        if (c == 'F'){
            scanf("%d",&b);
            b--;
            if (A == b)
                printf("0");
            else if (b < A){
                int x = query(1, 0, n - 1, b, A - 1);
                int y = bs(A + 1, n - 1, x, true);
                printf("%d", abs(A - y) + abs(A - b));
            }
            else{
                int x = query(1, 0, n - 1, A + 1, b);
                int y = bs(0, A - 1, x, false);
                printf("%d", abs(A - y) + abs(A - b));
            }
            printf("\n");
        }
        else{
            scanf("%d %d",&i,&e);
            int v = *s.rbegin() + 1;
            e--;
            i--;
            for(auto it = s.rbegin() ; e ; it++,e--){
                v = *it;
                update(1, 0, n - 1, pos[*it], (*it)+1);
            }
            update(1, 0, n - 1, i, v);
            if (sz(s) > 10)
                s.erase(s.begin());
        }
    }
}

Compilation message

cake.cpp: In function 'void IO()':
cake.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.txt","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:100: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:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~
cake.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&c);
         ~~~~~^~~~~~~~~~
cake.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~
cake.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&i,&e);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 35 ms 1400 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1101 ms 24348 KB Output is correct
2 Correct 618 ms 24440 KB Output is correct
3 Correct 734 ms 24440 KB Output is correct
4 Correct 421 ms 24568 KB Output is correct
5 Correct 1181 ms 25468 KB Output is correct
6 Correct 982 ms 25436 KB Output is correct
7 Correct 742 ms 25336 KB Output is correct
8 Correct 458 ms 25336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 7456 KB Output is correct
2 Correct 327 ms 7032 KB Output is correct
3 Correct 311 ms 6904 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 630 ms 15864 KB Output is correct
6 Correct 622 ms 15736 KB Output is correct
7 Correct 485 ms 15672 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1784 KB Output is correct
2 Correct 100 ms 1912 KB Output is correct
3 Correct 229 ms 5412 KB Output is correct
4 Correct 272 ms 5368 KB Output is correct
5 Correct 367 ms 4472 KB Output is correct
6 Correct 458 ms 8184 KB Output is correct
7 Correct 357 ms 6136 KB Output is correct
8 Correct 384 ms 15756 KB Output is correct
9 Execution timed out 2032 ms 28080 KB Time limit exceeded
10 Correct 1256 ms 13564 KB Output is correct
11 Correct 1572 ms 15612 KB Output is correct
12 Execution timed out 2089 ms 25852 KB Time limit exceeded
13 Execution timed out 2064 ms 28016 KB Time limit exceeded