oj.uz

답안 #251015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251015 2020-07-19T23:37:28 Z Amine 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 30532 KB 
#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;

pair<int,int> st[N];

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

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

int query(int idx, int l, int r, int ql, int qr){
    if (l >= ql && r <= qr)
        return st[idx].s;
    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:17: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
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1221 ms 24772 KB Output isn't correct
2 Incorrect 667 ms 24956 KB Output isn't correct
3 Incorrect 789 ms 24952 KB Output isn't correct
4 Correct 467 ms 24824 KB Output is correct
5 Incorrect 1231 ms 25820 KB Output isn't correct
6 Incorrect 1112 ms 26104 KB Output isn't correct
7 Incorrect 822 ms 25848 KB Output isn't correct
8 Correct 486 ms 25808 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 475 ms 8312 KB Output isn't correct
2 Incorrect 339 ms 8240 KB Output isn't correct
3 Incorrect 327 ms 8184 KB Output isn't correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 646 ms 18040 KB Output isn't correct
6 Incorrect 674 ms 18040 KB Output isn't correct
7 Incorrect 500 ms 17656 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 147 ms 2040 KB Output isn't correct
2 Incorrect 101 ms 2296 KB Output isn't correct
3 Incorrect 241 ms 6136 KB Output isn't correct
4 Incorrect 299 ms 6136 KB Output isn't correct
5 Incorrect 384 ms 4604 KB Output isn't correct
6 Incorrect 477 ms 8952 KB Output isn't correct
7 Incorrect 374 ms 6648 KB Output isn't correct
8 Incorrect 433 ms 17144 KB Output isn't correct
9 Execution timed out 2076 ms 30532 KB Time limit exceeded
10 Incorrect 1276 ms 13672 KB Output isn't correct
11 Incorrect 1578 ms 15488 KB Output isn't correct
12 Execution timed out 2090 ms 27768 KB Time limit exceeded
13 Execution timed out 2074 ms 30352 KB Time limit exceeded