oj.uz

답안 #146641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146641 2019-08-24T19:00:02 Z 12tqian 케이크 (CEOI14_cake) C++14
63.3333 / 100
 2000 ms 30128 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] = max(lazy[ind], mx[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;
    f0r(it, 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 cnt = 0;
    for(auto x: queries){
        if(x.f == 0){
            int i = x.s.f;
            int e = x.s.s;
            if(i == a) {cnt++; continue;}
            beg[i] = num[cnt];
            mst.upd(i, num[cnt]);
            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 = a+1;
                int use = 0;
                while(idx <n){
                    if(beg[idx]>mx) break;
                    idx++;
                }
               // cout << mx << " " << idx << endl;

            }
            else{
                int mx = mst.query(a+1, b);
                idx = a-1;
                while(idx>=0){
                    if(beg[idx]>mx) break;
                    idx--;
                }
            }

            //if(b == 3) cout << idx<< " bad " << " " << mst.query(a+1, b) << " " << lst.qmax(0, a-1)<<  endl;
            cout << abs(b - a)+1 + abs(idx - a) - 1-1 << endl;

        }
    }
    /*f0r(i, n) cout << beg[i] << " ";
    cout << endl;
    f0r(i, sz(updates)) cout << num[i] << " ";*/
    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:230:17: warning: unused variable 'e' [-Wunused-variable]
             int e = x.s.s;
                 ^
cake.cpp:243:21: warning: unused variable 'use' [-Wunused-variable]
                 int use = 0;
                     ^~~
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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2420 KB Output is correct
2 Correct 5 ms 2424 KB Output is correct
3 Correct 5 ms 2552 KB Output is correct
4 Correct 13 ms 2680 KB Output is correct
5 Correct 33 ms 3192 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 24956 KB Output is correct
2 Correct 174 ms 24936 KB Output is correct
3 Correct 185 ms 24856 KB Output is correct
4 Correct 158 ms 24920 KB Output is correct
5 Correct 244 ms 25516 KB Output is correct
6 Correct 234 ms 30128 KB Output is correct
7 Correct 202 ms 29772 KB Output is correct
8 Correct 169 ms 29892 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 8896 KB Time limit exceeded
2 Correct 1937 ms 8592 KB Output is correct
3 Execution timed out 2064 ms 8560 KB Time limit exceeded
4 Correct 4 ms 2424 KB Output is correct
5 Execution timed out 2054 ms 12648 KB Time limit exceeded
6 Execution timed out 2069 ms 12404 KB Time limit exceeded
7 Execution timed out 2041 ms 12396 KB Time limit exceeded

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 4528 KB Output is correct
2 Correct 112 ms 4424 KB Output is correct
3 Correct 533 ms 7504 KB Output is correct
4 Correct 522 ms 7532 KB Output is correct
5 Correct 287 ms 7960 KB Output is correct
6 Correct 1255 ms 11764 KB Output is correct
7 Correct 541 ms 9760 KB Output is correct
8 Correct 183 ms 16740 KB Output is correct
9 Execution timed out 2064 ms 29920 KB Time limit exceeded
10 Correct 947 ms 20120 KB Output is correct
11 Correct 1882 ms 22948 KB Output is correct
12 Execution timed out 2063 ms 27436 KB Time limit exceeded
13 Execution timed out 2070 ms 28800 KB Time limit exceeded