Submission #1121285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121285		smokieboi	Cake (CEOI14_cake)	C++17	35 / 100	2065 ms	17548 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], Rank[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{
    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();
            }
    }
}

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;
    }
    do_sub1::solve();
}

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

Compilation message (stderr)

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

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