답안 #146603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146603 2019-08-24T17:30:21 Z 12tqian 케이크 (CEOI14_cake) C++14
0 / 100
1231 ms 29224 KB
#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();
}

const int MAX = 250005;
const int BIG = 10;
const int INF = 1e9;
int n, a;
int beg[MAX];
vector<pair<int, pii>> queries;
vpi updates;
vi num;
int rec[MAX];
vpi ord;


template<class T, int SZ> struct Seg { // SZ should be power of 2
    T ID = 0; // comb(ID,b) must equal b
    T comb(T a, T b) { return max(a, b); } // easily change this to min or max

    T seg[2*SZ];
    Seg() { memset(seg,0,sizeof seg); }

    void upd(int p, T value) {  // set value at position p
        seg[p += SZ] = value;
        for (p /= 2; p; p /= 2) seg[p] = comb(seg[2*p],seg[2*p+1]);
    }

    T query(int l, int r) {  // sum on interval [l, r]
        r ++; T lres = ID, rres = ID; // make sure non-commutative operations work
        for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
            if (l&1) lres = comb(lres,seg[l++]);
            if (r&1) rres = comb(seg[--r],rres);
        }
        return comb(lres,rres);
    }
};
template<class T, int SZ> struct seg {
    T mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
    //lazy is -1 if nothing, 0 if making all 0, 1, if making all 1
    void push(int ind, int L, int R) {
        if(lazy[ind] == -INF) return;
        mx[ind] = lazy[ind];
        if(L!= R) lazy[2*ind] = lazy[ind], lazy[2*ind+1] = lazy[ind];
        lazy[ind] = -INF;
    }
    void build(){
        f0r(i, 2*SZ) lazy[i] = -INF;
    }
    void pull(int ind) {
        mx[ind] = max(mx[2*ind], mx[2*ind+1]);
    }

    T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return mx[ind];

        int M = (L+R)/2;
        return max(qmax(lo,hi,2*ind,L,M),qmax(lo,hi,2*ind+1,M+1,R));
    }

    void upd(int lo, int hi, long long inc, int ind = 1, int L = 0, int R = SZ-1) {
        //cout << lo << " " << hi << "  " << L << " "<< R << " asdf\n";
        push(ind,L,R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
           // cout << L << " " << R << " " << lazy[ind] << endl;
            push(ind,L,R);
            return;
        }
        int M = (L+R)/2;
        upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
        pull(ind);
    }
    ///find right most greater than x
    int lsearch(int x, int ind = 1, int L = 0, int R = SZ-1){
        int M = (L + R)/2;
        push(ind, L, R);
        if(L != R) push(2*ind, L, M);
        if(L!= R) push(2*ind+1, M+1, R);
        if(mx[ind] <x) return -1;
        if(L == R) return L;
        //int M = (L + R)/2;
        if(mx[2*ind+1]>x){
            return lsearch(x, 2*ind+1, M+1, R);
        }
        else{
            return lsearch(x, 2*ind, L, M);
        }
    }
    int rsearch(int x, int ind = 1, int L = 0, int R = SZ-1){
        int M = (L + R)/2;
        push(ind, L, R);
        if(L != R) push(2*ind, L, M);
        if(L!= R) push(2*ind+1, M+1, R);
        if(mx[ind] <x) return n;
        if(L == R) return L;

        if(mx[2*ind]>x){
            return rsearch(x, 2*ind, L, M);
        }
        else{
            return rsearch(x, 2*ind+1, M+1, R);
        }
    }
};
Seg<int, (1<<18)> mst;
seg<int, (1<<18)> lst;
seg<int, (1<<18)> rst;
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;
    }
    int q;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'E'){
            int i, e;
            cin >> i >> e;
            i--; e--;
            queries.eb(mp(0, mp(i, e)));
            updates.eb(mp(i, e));
        }
        else{
            int b;
            cin >> b;
            b--;
            queries.eb(mp(1, mp(b, -1)));
        }
    }
    sort(all(d));
    int time = 0;
    for(auto x: d) ord.eb(mp(x.s, time));
    time++;
    for(auto x: updates){
        vpi pop;
        int cur = 0;
        while(cur<x.s){
            int last = sz(ord) - 1;
            if(rec[ord[last].f] == ord[last].s){
                cur++;
            }
            pop.eb(ord[last]);
            ord.pop_back();
        }
        rec[x.f] = time;
        ord.eb(mp(x.f, time));
        reverse(all(pop));
        for(auto y: pop) ord.eb(y);
        time++;
    }
    //return 0;
    num.resize(sz(ord));
    f0r(i, sz(ord)){
        if(ord[i].s == 0){
            beg[ord[i].f] = i;
        }
        else{
            num[ord[i].s - 1] = i;
        }
    }
    f0r(i, n){
        mst.upd(i, beg[i]);
    }
    int cur = 0;
    f1r(i, a+1, n){
        cur = max(cur, beg[i]);
        rst.upd(i, i, cur);
    }
    cur = 0;
    for(int i = a-1; i>= 0; i--){
        cur = max(cur, beg[i]);
        lst.upd(i, i, cur);
    }
    int cnt = 0;
    for(auto x: queries){
        if(x.f == 0){
            int i = x.s.f;
            int e = x.s.s;
            if(i == a) continue;
            mst.upd(i, num[cnt]);
            if(i>a){
                if(a+1<n) rst.upd(a+1, i, num[cnt]);
            }
            else{
                if(a-1>=0) lst.upd(0, a-1, num[cnt]);
            }
            /*f0r(i, n) cout << mst.query(i, i) << " ";
            cout << endl;
            f0r(i, n) cout << lst.qmax(i, i) << " ";
            cout << endl;
            f0r(i, n) cout << rst.qmax(i, i) << " ";
            cout << endl;*/
            cnt++;
        }
        else{
            int b = x.s.f;
            if(b == a){cout << 0 << endl; continue;}
            int idx;
            if(b<a){
                int mx = mst.query(b, a-1);
                idx = rst.rsearch(mx);

            }
            else{
                int mx = mst.query(a+1, b);
                idx = lst.lsearch(mx);
            }
            cout << abs(b - a)+1 + abs(idx - a) - 1-1 << endl;

        }
    }
    return 0;
}

Compilation message

cake.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
cake.cpp: In function 'int main()':
cake.cpp:242:17: warning: unused variable 'e' [-Wunused-variable]
             int e = x.s.s;
                 ^
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);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 417 ms 21220 KB Output isn't correct
2 Incorrect 300 ms 21264 KB Output isn't correct
3 Incorrect 331 ms 21216 KB Output isn't correct
4 Correct 265 ms 21124 KB Output is correct
5 Incorrect 399 ms 21856 KB Output isn't correct
6 Incorrect 371 ms 25320 KB Output isn't correct
7 Incorrect 382 ms 25224 KB Output isn't correct
8 Correct 290 ms 25224 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 356 ms 10568 KB Output isn't correct
2 Incorrect 349 ms 10284 KB Output isn't correct
3 Incorrect 340 ms 10172 KB Output isn't correct
4 Correct 4 ms 2552 KB Output is correct
5 Incorrect 448 ms 15848 KB Output isn't correct
6 Incorrect 444 ms 14452 KB Output isn't correct
7 Incorrect 425 ms 14160 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 4016 KB Output isn't correct
2 Incorrect 100 ms 4320 KB Output isn't correct
3 Incorrect 181 ms 7564 KB Output isn't correct
4 Incorrect 187 ms 7676 KB Output isn't correct
5 Incorrect 291 ms 7448 KB Output isn't correct
6 Incorrect 338 ms 11548 KB Output isn't correct
7 Incorrect 381 ms 8868 KB Output isn't correct
8 Incorrect 218 ms 14516 KB Output isn't correct
9 Incorrect 1231 ms 29224 KB Output isn't correct
10 Incorrect 960 ms 17060 KB Output isn't correct
11 Incorrect 1006 ms 19692 KB Output isn't correct
12 Incorrect 1193 ms 26288 KB Output isn't correct
13 Incorrect 1170 ms 28380 KB Output isn't correct