oj.uz

Submission #251020

# Submission time Handle Problem Language Result Execution time Memory
251020 2020-07-20T00:11:00 Z Amine Cake (CEOI14_cake) C++14
100 / 100
 1935 ms 29736 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 1 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 31 ms 1400 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 25320 KB Output is correct
2 Correct 535 ms 25208 KB Output is correct
3 Correct 652 ms 25212 KB Output is correct
4 Correct 390 ms 25224 KB Output is correct
5 Correct 1089 ms 26188 KB Output is correct
6 Correct 892 ms 26104 KB Output is correct
7 Correct 675 ms 26104 KB Output is correct
8 Correct 408 ms 26108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 8056 KB Output is correct
2 Correct 300 ms 7800 KB Output is correct
3 Correct 291 ms 7800 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 531 ms 16764 KB Output is correct
6 Correct 584 ms 16700 KB Output is correct
7 Correct 439 ms 16356 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2240 KB Output is correct
2 Correct 88 ms 2296 KB Output is correct
3 Correct 208 ms 6268 KB Output is correct
4 Correct 269 ms 6264 KB Output is correct
5 Correct 341 ms 5112 KB Output is correct
6 Correct 399 ms 8952 KB Output is correct
7 Correct 318 ms 7032 KB Output is correct
8 Correct 363 ms 16760 KB Output is correct
9 Correct 1935 ms 29736 KB Output is correct
10 Correct 1163 ms 14200 KB Output is correct
11 Correct 1359 ms 14840 KB Output is correct
12 Correct 1843 ms 26352 KB Output is correct
13 Correct 1911 ms 28864 KB Output is correct