oj.uz

답안 #146605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146605 2019-08-24T17:51:54 Z 12tqian 케이크 (CEOI14_cake) C++14
0 / 100
 1260 ms 35220 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;
    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);
            }
           // if(b == 3) cout << idx<< " bad " << endl;
            cout << abs(b - a)+1 + abs(idx - a) - 1-1 << endl;

        }
    }
    /*cout << q << endl;
    f0r(i, n) cout << beg[i] << " ";
    cout << endl;
    f0r(i, q) 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: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 403 ms 25344 KB Output isn't correct
2 Incorrect 305 ms 25220 KB Output isn't correct
3 Incorrect 339 ms 25216 KB Output isn't correct
4 Correct 270 ms 25356 KB Output is correct
5 Incorrect 415 ms 26036 KB Output isn't correct
6 Incorrect 380 ms 30052 KB Output isn't correct
7 Incorrect 393 ms 29820 KB Output isn't correct
8 Correct 290 ms 29836 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 362 ms 10560 KB Output isn't correct
2 Incorrect 355 ms 10348 KB Output isn't correct
3 Incorrect 341 ms 10328 KB Output isn't correct
4 Correct 4 ms 2552 KB Output is correct
5 Incorrect 449 ms 16928 KB Output isn't correct
6 Incorrect 440 ms 16744 KB Output isn't correct
7 Incorrect 423 ms 16616 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 105 ms 4580 KB Output isn't correct
2 Incorrect 103 ms 4596 KB Output isn't correct
3 Incorrect 183 ms 8512 KB Output isn't correct
4 Incorrect 190 ms 8620 KB Output isn't correct
5 Incorrect 292 ms 8208 KB Output isn't correct
6 Incorrect 341 ms 12896 KB Output isn't correct
7 Incorrect 387 ms 10148 KB Output isn't correct
8 Incorrect 229 ms 16632 KB Output isn't correct
9 Incorrect 1260 ms 35220 KB Output isn't correct
10 Incorrect 969 ms 20396 KB Output isn't correct
11 Incorrect 1016 ms 23512 KB Output isn't correct
12 Incorrect 1201 ms 31968 KB Output isn't correct
13 Incorrect 1167 ms 34368 KB Output isn't correct