제출 #1121438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121438		smokieboi	케이크 (CEOI14_cake)	C++17	35 / 100	2075 ms	17556 KiB

cake

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl '\n'
#define fu(i,a,b) for(int i=a; i<=b; i++)
#define fd(i,a,b) for(int i=a; i>=b; i--)
#define BIT(i, n) (((n)>>(i))&(1))
#define pii pair<int, int>
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define SZ(V) (int)(V.size())
#define pb push_back
#define eb emplace_back
#define NAME "quan"

int t,n,m,k,q;

const int N = 25e4 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 7;

void add(int &a, int b) {a+=b; if(a>=MOD) a-=MOD;}
void sub(int &a, int b) {a-=b; if(a<0) a+=MOD;}


int x, cnt;
pii a[N];
int ans[N], pos[N];

struct Query{
    char type;
    int idx, x;
} Q[2*N];

void calc(){
    int L = x-1;
    int R = x+1;
    int c = 1;
    while(1 <= L || R <= n){
        if(pos[L] > pos[R]) ans[L--] = c;
        else ans[R++] = c;
        c++;
    }
}

bool checksub1(){
    return cnt*n <= 2e8;
}

namespace do_sub1{

    int Rank[N];

    void solve(){
        sort(a+1, a+n+1, greater<>());
        fu(i,1,n){
            Rank[i] = a[i].ss;
            pos[a[i].ss] = i;
        }
        pos[0] = pos[n+1] = -1;
        calc();
        fu(i,1,q)
            if(Q[i].type == 'F') cout << ans[Q[i].idx] << nl;
            else{
                fd(j, pos[Q[i].idx], Q[i].x+1)
                    ++pos[Rank[j-1]],
                    Rank[j] = Rank[j-1];
                pos[Q[i].idx] = Q[i].x;
                Rank[Q[i].x] = Q[i].idx;
                calc();
            }
    }
}

bool checksub2(){
    return (q - cnt)*cnt <= 2e8;
}

namespace do_sub2{

    bool used[N];
    pii Rank[N];

    void solve(){
        fu(i,1,q)
            if(Q[i].type == 'F') used[Q[i].idx] = true;
        sort(a+1, a+n+1, greater<>());
        fu(i,1,n)
            if(used[a[i].ss]){
                Rank[++t] = {a[i].ss, i};
                pos[a[i].ss] = t;
            }
        pos[0] = pos[n+1] = -1;
        calc();
        fu(i,1,q)
            if(Q[i].type == 'F') cout << ans[Q[i].idx] << nl;
            else{
                int it = pos[Q[i].idx]-1;
                while(Rank[it].ss >= Q[i].x){
                    Rank[it+1] = Rank[it];
                    ++Rank[it+1].ss;
                    ++pos[Rank[it+1].ff]; 
                    --it;
                }
                pos[Q[i].idx] = it+1;
                Rank[it+1] = {Q[i].idx, Q[i].x};
                calc();
            }
    }
}

void nhap(){
    cin >> n >> x;
    fu(i,1,n){
        cin >> a[i].ff;
        a[i].ss = i;
    }
    cin >> q;
    fu(i,1,q){
        cin >> Q[i].type;
        if(Q[i].type == 'F') cin >> Q[i].idx;
        else{
            cin >> Q[i].idx >> Q[i].x;
            ++cnt;
        }
    }
    if(checksub1()){
        do_sub1::solve();
        return;
    }
    if(checksub2()){
        do_sub2::solve();
        return;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(NAME".inp", "r")){
       freopen(NAME".inp", "r", stdin);
       freopen(NAME".out", "w", stdout);
    }
    nhap();
}

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

cake.cpp: In function 'int main()':
cake.cpp:143:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |        freopen(NAME".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:144:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |        freopen(NAME".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50