제출 #146436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146436		12tqian	케이크 (CEOI14_cake)	C++14	0 / 100	1223 ms	15464 KiB

cake

#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
struct node{
    int nxt, bef, val;
};
const int MAX = 250005;
const int BIG = 10;
int n, a;

node ord[MAX];
int link[MAX];
int beg[MAX];
int head, tail;
void del(int x){
    if(ord[x].val == tail){
        ord[(ord[x].bef)].nxt = head;
        tail = ord[x].bef;
        ord[head].bef = tail;
    }
    else if(ord[x].val == head){
        ord[(ord[x].nxt)].bef = tail;
        head = ord[x].nxt;
        ord[tail].bef = head;
    }
    else{
        ord[(ord[x].bef)].nxt = ord[x].nxt;
        ord[(ord[x].nxt)].bef = ord[x].bef;
    }
}
vi check;
vi num;
void redo(int i, int e){
    if(i == a) return;
    int mn = e;
    f0r(j, sz(check)){
        if(i<a){
            if(check[j]>a) continue;
            if(i<check[j]){
                mn = min(mn, num[j]);
            }
        }
        else{
            if(check[j]<a) continue;
            if(i>check[j]){
                mn = min(mn, num[j]);
            }
        }
    }
   // if(i == 3){cout << mn <<" min" << endl;}
    if(i<a) link[i] = n;
    else link[i] = -1;
    f0r(j, sz(check)){
        if(i<a){
            if(check[j]<a) continue;
            if(link[i]>check[j] && num[j]<mn) link[i] = check[j];

        }
        else{
            if(check[j]>a) continue;
            if(link[i]<check[j] && num[j]<mn) link[i] = check[j];
        }
    }

}
void ins(int x, int r){
    del(x);
    int cur = head;
    if(r == 0){
        int rep = head;
        ord[x].nxt = rep;
        ord[x].bef = tail;
        ord[rep].bef = ord[x].val;
        head = ord[x].val;
        ord[tail].nxt = head;
    }
    else if(r == n-1){
        int rep = tail;
        ord[x].bef = rep;
        ord[x].nxt = head;
        ord[rep].nxt = ord[x].val;
        tail = ord[x].val;
        ord[head].bef = tail;
    }
    else{
        int rep = head;

        f0r(i, r){
            rep = ord[rep].nxt;
        }
        ord[x].nxt = rep;
        ord[x].bef = ord[rep].bef;
        ord[ord[rep].bef].nxt = ord[x].val;
        ord[rep].bef = ord[x].val;

    }
}
int main(){
    fast_io();
    cin >> n >> a;
    a--;
    vpi d;
    f0r(i, n){
        int di;
        cin >> di;
        d.eb(mp(di, i));
        beg[i] = di;
    }
    sort(all(d));
    reverse(all(d));
    f0r(i, n){
        ord[i].val = i;
        ord[i].nxt = -1;
        ord[i].bef = -1;
    }
    f0r(i, sz(d)){
        int j = (i+1)%n;
        ord[d[i].s].nxt = ord[d[j].s].val;
        ord[d[j].s].bef = ord[d[i].s].val;
        if(i == 0) head = ord[d[i].s].val;
        if(i == sz(d)-1) tail = ord[d[i].s].val;
    }
    int cnt = head;
    while(true){
        if(ord[cnt].nxt == head) break;
        cnt = ord[cnt].nxt;
    }
    int mx = 0;
    int idx = a+1;
    for(int i = a-1; i>= 0; i--){
        mx = max(mx, beg[i]);
        while(idx<n){
            if(mx>beg[idx]) idx++;
            else break;
        }
        link[i] = idx;
    }
    mx = 0;
    idx = a-1;
    for(int i = a+1; i<n; i++){
        mx = max(mx, beg[i]);
        while(idx>0){
            if(mx>beg[idx]) idx--;
            else break;
        }
        link[i] = idx;
    }
    link[a] = a;
    int q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'E'){
            int i, e;
            cin >> i >> e;
            i--; e--;
            if(i == a) continue;
            ins(i, e);
            check.clear();
            num.clear();
            int cnt = 0;
            int st = head;
            while(cnt<BIG){
                if(st != a){
                    check.eb(st);
                    num.eb(cnt);
                }
                cnt++;
                st = ord[st].nxt;
                if(st == head) break;
            }
         //  cout << check << " " << num << endl;
            f0r(j, sz(check)) redo(check[j], num[j]);
            int cur = head;
          /*  f0r(i, n){
                cout << cur << " " << ord[cur].bef << " " << ord[cur].nxt << endl;
                cur = ord[cur].nxt;
            }
            cout << endl;
            f0r(i, n){
                cout << i << " " << link[i] << endl;
            }*/
        }
        else{
            int b;
            cin >> b;
            b--;
            if(b == a) cout << 1 - 1<< endl;
            else cout << abs(b - a)+1 + abs(link[b] - a) - 1-1 << endl;
        }
    }
    return 0;
}

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

cake.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
cake.cpp: In function 'void ins(int, int)':
cake.cpp:120:9: warning: unused variable 'cur' [-Wunused-variable]
     int cur = head;
         ^~~
cake.cpp: In function 'int main()':
cake.cpp:227:17: warning: unused variable 'cur' [-Wunused-variable]
             int cur = head;
                 ^~~
cake.cpp: In function 'void io(std::__cxx11::string)':
cake.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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