답안 #347633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
347633 2021-01-13T09:39:34 Z ACmachine 케이크 (CEOI14_cake) C++17
0 / 100
1384 ms 13424 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 + 1 == end){
            if(tree[v].ans >= val)
                return beg;
            else
                return -1;
        }
        if(beg >= r || end <= l){
            return -1;
        }
        if(beg >= l && end <= r){
            if(tree[v].ans < val) 
                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 + 1 == end){
            if(tree[v].ans >= val)
                return beg;
            else
                return -1;
        }
        if(beg >= r || end <= l){
            return -1;
        }
        if(beg >= l && end <= r){
            if(tree[v].ans < val) 
                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;
    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, 10){
                indices[x][0] = st.find_id(curr_m, left, st.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++;
            }
            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[8][1]);
            }
        }
        else{
            int b; cin >> b;
            b--;
            int valb = st.query(b, b + 1, 0, st.n, 1).ans;
            if(a == b){
                cout << 0 << "\n";
            }
            else if(b > a){
                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 id = st.find_id(valb, a+1, n, 0, st.n, 1);
                /* dbg(a + 1) */
                /* dbg(id) */ 
                if(id == -1){
                    id = n - 1;
                }
                int ans = a - b + (id - a);
                cout << ans << "\n";
            }
        }
    }
	
    return 0;
}

Compilation message

cake.cpp: In member function 'void segtree::build(std::vector<int>&)':
cake.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             if(i < init.size()){
      |                ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1289 ms 5244 KB Output isn't correct
2 Incorrect 1219 ms 5228 KB Output isn't correct
3 Incorrect 1231 ms 5064 KB Output isn't correct
4 Incorrect 1076 ms 5064 KB Output isn't correct
5 Incorrect 1384 ms 5868 KB Output isn't correct
6 Incorrect 1349 ms 6252 KB Output isn't correct
7 Incorrect 1314 ms 6124 KB Output isn't correct
8 Incorrect 1127 ms 6252 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 74 ms 4716 KB Output isn't correct
2 Incorrect 64 ms 4588 KB Output isn't correct
3 Incorrect 60 ms 4588 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 97 ms 8428 KB Output isn't correct
6 Incorrect 90 ms 8496 KB Output isn't correct
7 Incorrect 80 ms 8300 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 876 KB Output isn't correct
2 Incorrect 74 ms 1004 KB Output isn't correct
3 Incorrect 157 ms 2668 KB Output isn't correct
4 Incorrect 157 ms 2668 KB Output isn't correct
5 Incorrect 190 ms 1772 KB Output isn't correct
6 Incorrect 296 ms 4844 KB Output isn't correct
7 Incorrect 306 ms 2668 KB Output isn't correct
8 Incorrect 617 ms 5612 KB Output isn't correct
9 Incorrect 1171 ms 13292 KB Output isn't correct
10 Incorrect 636 ms 5228 KB Output isn't correct
11 Incorrect 937 ms 6528 KB Output isn't correct
12 Incorrect 1172 ms 12780 KB Output isn't correct
13 Incorrect 1105 ms 13424 KB Output isn't correct