제출 #251015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251015		Amine	케이크 (CEOI14_cake)	C++14	0 / 100	2090 ms	30532 KiB

cake

#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());
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50