답안 #347741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347741 2021-01-13T10:52:17 Z ACmachine 케이크 (CEOI14_cake) C++17
92.5 / 100
2000 ms 7408 KB
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

struct node{
    int ans = 0;
    int id = 0;
    void apply(int val){
        ans = val;
    }
};
struct segtree{
    int n;
    vector<node> tree;
    segtree(int _n){
        n = 1;
        while(n < _n) n *= 2;
        tree.resize(2 * n);
    }
    node comb(node lhs, node rhs){
        node res;
        res.ans = max(lhs.ans, rhs.ans);
        if(lhs.ans > rhs.ans){
            res.id = lhs.id;
        }
        else{
            res.id = rhs.id;
        }
        return res;
    }
    void build(vector<int> &init){
        REP(i, n){ 
            if(i < init.size()){
                tree[i + n].ans = init[i];
                tree[i + n].id = i;
            }
        }
        FORD(i, n-1, 1, 1)
            tree[i] = comb(tree[i<<1], tree[i<<1|1]);
    }
    void upd(int pos, int val, int beg, int end, int v){
        if(beg + 1 == end){
            tree[v].apply(val);
            return;
        }
        int mid = (beg + end) >> 1;
        if(pos < mid){
            upd(pos, val, beg, mid, v << 1);
        }
        else{
            upd(pos, val, mid, end, v << 1 | 1);
        }
        tree[v] = comb(tree[v<<1], tree[v<<1|1]);
    }
    node query(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r){
            return tree[v];
        }
        if(beg >= r || end <= l){
            node res;
            res.ans = -INF;
            return res;
        }
        int mid = (beg + end) >> 1;
        return comb(query(l, r, beg, mid, v << 1), query(l, r, mid, end, v << 1 | 1));
    }
    int find_id(int val, int l, int r, int beg, int end, int v){ 
        if(beg >= r || end <= l){
            return -1;
        }
        if(beg >= l && end <= r){
            if(tree[v].ans < val) 
                return -1;
        }
        if(beg + 1 == end){
            if(tree[v].ans >= val)
                return beg;
            else
                return -1;
        }
        int mid = (beg + end) >> 1;
        int left = find_id(val, l, r, beg, mid, v << 1);
        if(left != -1) return left;
        else return find_id(val, l, r, mid, end, v<<1|1);
    }
    int find_id_last(int val, int l, int r, int beg, int end, int v){ 
        if(beg >= r || end <= l){
            return -1;
        }
        if(beg >= l && end <= r){
            if(tree[v].ans < val) 
                return -1;
        }
        if(beg + 1 == end){
            if(tree[v].ans >= val)
                return beg;
            else
                return -1;
        }
        int mid = (beg + end) >> 1;
        int left = find_id_last(val, l, r, mid, end, v << 1|1);
        if(left != -1) return left;
        else return find_id_last(val, l, r, beg, mid, v<<1);
    }
};
    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int n, a;
    cin >> n >> a;
    a--;
    segtree st(n);
    vi d(n); cin >> d;
    st.build(d);
    int q; cin >> q;
    int curr_m = n - 9;
    array<array<int, 2>, 10> indices;
    int topx = min(10, n);
    REP(qq, q){
        char t; cin >> t;
        if(t == 'E'){
            int i, e;
            cin >> i >> e;
            i--;
            int x = 0;
            int left = 0;
            REP(j, topx){
                indices[x][0] = st.find_id(curr_m, left, n, 0, st.n, 1);
                indices[x][1] = st.query(indices[x][0], indices[x][0] + 1, 0, st.n, 1).ans;
                left = indices[x][0] + 1;
                x++; 
            }
            /* cout << "E:" << "\n"; */
            /* REP(j, topx){ */
            /*     cout << indices[j][0] << " " << indices[j][1] << "\n"; */
            /* } */
            /* cout << ":E" << "\n"; */
            sort(all(indices), [](array<int, 2> &lhs, array<int, 2> &rhs){return lhs[1] > rhs[1];});
            REP(j, e - 1){
                st.upd(indices[j][0], indices[j][1] + 1, 0, st.n, 1);
                indices[j][1]++;
            }
            
            int vali = st.query(i, i+1, 0, st.n, 1).ans;
            st.upd(i, indices[e-1][1] + 1, 0, st.n, 1);
            if(vali < curr_m){
                curr_m = min(indices[e-1][1] + 1, indices[topx - 2][1]);
            } 
        }
        else{
            int b; cin >> b;
            b--;
            if(a == b){
                cout << 0 << "\n";
            }
            else if(b > a){
                int valb = st.query(a + 1, b + 1, 0, st.n, 1).ans; 
                int id = st.find_id_last(valb, 0, a, 0, st.n, 1);
                id++;
                int ans = b - a + (a - id);
                cout << ans << "\n"; 
            }
            else{
                int valb = st.query(b, a, 0, st.n, 1).ans; 
                int id = st.find_id(valb, a+1, n, 0, st.n, 1);
                id--;
                if(id == -2){
                    id = n - 1;
                }
                int ans = a - b + (id - a);
                cout << ans << "\n";
            }
        } 
        /* REP(i, 5){ */
        /*     cout << st.query(i, i + 1, 0, st.n, 1).ans << " "; */
        /* } */
        /* cout << "\n"; */
    }
	
    return 0;
}

Compilation message

cake.cpp: In member function 'void segtree::build(std::vector<int>&)':
cake.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             if(i < init.size()){
      |                ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 11 ms 364 KB Output is correct
5 Correct 29 ms 620 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1962 ms 620 KB Output is correct
2 Correct 1578 ms 620 KB Output is correct
3 Correct 1775 ms 620 KB Output is correct
4 Correct 1315 ms 696 KB Output is correct
5 Execution timed out 2088 ms 1004 KB Time limit exceeded
6 Correct 1820 ms 1004 KB Output is correct
7 Correct 1931 ms 1004 KB Output is correct
8 Correct 1345 ms 1132 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 3436 KB Output is correct
2 Correct 70 ms 3308 KB Output is correct
3 Correct 63 ms 3180 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 114 ms 6252 KB Output is correct
6 Correct 100 ms 6124 KB Output is correct
7 Correct 77 ms 5868 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 620 KB Output is correct
2 Correct 122 ms 620 KB Output is correct
3 Correct 238 ms 1940 KB Output is correct
4 Correct 255 ms 2060 KB Output is correct
5 Correct 337 ms 748 KB Output is correct
6 Correct 500 ms 3180 KB Output is correct
7 Correct 530 ms 1260 KB Output is correct
8 Correct 948 ms 2940 KB Output is correct
9 Correct 1968 ms 7408 KB Output is correct
10 Correct 1127 ms 1900 KB Output is correct
11 Correct 1501 ms 2392 KB Output is correct
12 Correct 1960 ms 6892 KB Output is correct
13 Correct 1717 ms 7292 KB Output is correct