oj.uz

Submission #251019

# Submission time Handle Problem Language Result Execution time Memory
251019 2020-07-20T00:10:32 Z Amine Cake (CEOI14_cake) C++14
0 / 100
 618 ms 1048580 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(){
    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    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:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("in.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:102: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:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~
cake.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&c);
         ~~~~~^~~~~~~~~~
cake.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~
cake.cpp:134: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 618 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 524 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 519 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 537 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 542 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 555 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 536 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 533 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 529 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 515 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 529 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 572 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 544 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 517 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 524 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 511 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 531 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 525 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 513 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 533 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 524 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 536 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 523 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 504 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 506 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 512 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 557 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 515 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 508 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)