oj.uz

답안 #146642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146642 2019-08-24T19:11:25 Z 12tqian 케이크 (CEOI14_cake) C++14
100 / 100
 1190 ms 27400 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;
///find right that's greater than x
int binl(int l, int r, int x){
    if(mst.query(l, r) <x) return -1;
    while(abs(l-r)>1){
        int m = (l+r)/2;
        int val = mst.query(m, a-1);
        if(val>x){
            l = m;
        }
        else{
            r = m-1;
        }
    }
    if(l>r) swap(l, r);
    if(mst.query(r, a-1) >x) return r;
    return l;
}
int binr(int l, int r, int x){
    if(mst.query(l, r)<x) return n;
    while(abs(l-r)>1){
        int m = (l+r)/2;
        int val = mst.query(a+1, m);
        if(val>x){
            r = m;
        }
        else l = m+1;
    }
    if(l>r) swap(l, r);
    if(mst.query(a+1, l)>x) return l;
    return r;
}
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;
  //  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]);
            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);
                if(a+1<n) idx = binr(a+1, n-1, mx);
                else idx = n;

            }
            else{
                int mx = mst.query(a+1, b);
                if(a>0) idx = binl(0, a-1, mx);
                else idx = -1;
            }
            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:262: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
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 22588 KB Output is correct
2 Correct 173 ms 22400 KB Output is correct
3 Correct 187 ms 23116 KB Output is correct
4 Correct 154 ms 22868 KB Output is correct
5 Correct 242 ms 23304 KB Output is correct
6 Correct 232 ms 27400 KB Output is correct
7 Correct 200 ms 27372 KB Output is correct
8 Correct 167 ms 27244 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 8748 KB Output is correct
2 Correct 354 ms 8556 KB Output is correct
3 Correct 335 ms 8420 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 425 ms 12652 KB Output is correct
6 Correct 407 ms 12520 KB Output is correct
7 Correct 385 ms 12136 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 4272 KB Output is correct
2 Correct 97 ms 4308 KB Output is correct
3 Correct 175 ms 7532 KB Output is correct
4 Correct 171 ms 7532 KB Output is correct
5 Correct 277 ms 7940 KB Output is correct
6 Correct 310 ms 11616 KB Output is correct
7 Correct 362 ms 9752 KB Output is correct
8 Correct 116 ms 15968 KB Output is correct
9 Correct 1185 ms 26720 KB Output is correct
10 Correct 912 ms 18712 KB Output is correct
11 Correct 949 ms 21040 KB Output is correct
12 Correct 1190 ms 24464 KB Output is correct
13 Correct 1077 ms 25552 KB Output is correct