oj.uz

답안 #146620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146620 2019-08-24T18:23:01 Z 12tqian 케이크 (CEOI14_cake) C++14
10 / 100
 1327 ms 34612 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 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;
  //  cout << queries << endl;
    for(auto x: queries){
        if(x.f == 0){
            int i = x.s.f;
            int e = x.s.s;
            if(i == a) {cnt++; continue;}
            mst.upd(i, num[cnt]);
            if(i>a){
                rst.upd(i, n-1, num[cnt]);
            }
            else{
                lst.upd(0, i, num[cnt]);
            }
           /* cout <<i << " " << e << " " <<  cnt << " upd " << num[cnt] << endl;
            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);
            }

            //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:243: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2552 KB Output is correct
2 Incorrect 5 ms 2552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 428 ms 25364 KB Output is correct
2 Correct 335 ms 25292 KB Output is correct
3 Incorrect 367 ms 25212 KB Output isn't correct
4 Correct 309 ms 25212 KB Output is correct
5 Incorrect 444 ms 26116 KB Output isn't correct
6 Incorrect 424 ms 29960 KB Output isn't correct
7 Incorrect 417 ms 29972 KB Output isn't correct
8 Correct 340 ms 30032 KB Output is correct

Subtask #3
10.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 359 ms 10536 KB Output isn't correct
2 Incorrect 353 ms 10336 KB Output isn't correct
3 Correct 346 ms 10344 KB Output is correct
4 Correct 4 ms 2552 KB Output is correct
5 Correct 457 ms 16872 KB Output is correct
6 Correct 439 ms 16872 KB Output is correct
7 Correct 427 ms 16620 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 103 ms 4400 KB Output isn't correct
2 Incorrect 104 ms 4560 KB Output isn't correct
3 Incorrect 187 ms 8428 KB Output isn't correct
4 Incorrect 190 ms 8496 KB Output isn't correct
5 Incorrect 302 ms 8260 KB Output isn't correct
6 Incorrect 359 ms 12776 KB Output isn't correct
7 Incorrect 401 ms 10020 KB Output isn't correct
8 Incorrect 237 ms 16740 KB Output isn't correct
9 Incorrect 1327 ms 34612 KB Output isn't correct
10 Incorrect 978 ms 20316 KB Output isn't correct
11 Incorrect 1037 ms 23600 KB Output isn't correct
12 Incorrect 1277 ms 31656 KB Output isn't correct
13 Incorrect 1193 ms 33620 KB Output isn't correct