Submission #153415

#	Time	Username	Problem	Language	Result	Execution time	Memory
153415		Mercenary	케이크 (CEOI14_cake)	C++14	100 / 100	955 ms	5088 KiB

cake

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 250000 + 5;
int n , q , a;
int d[maxn];

struct IT{
    int s[maxn * 4];
//    int s1[maxn * 4];
//    void push(int x , bool key){
//        s[x] += lz[x];
//        if(key == 1){
//            lz[x * 2] += lz[x];
//            lz[x * 2 + 1] += lz[x];
//        }
//        lz[x] = 0;
//    }
    void build(int x,int l , int r){
        if(l == r){
            s[x] = d[l];
            return;
        }
        int mid = l + r >> 1;
        build(x * 2 , l , mid);
        build(x * 2 + 1 , mid + 1 , r);
        s[x] = min(s[x * 2] , s[x * 2 + 1]);
    }
//    void update(int x , int l , int r , int pos){
////        push(x , l != r);
//        if(l == r){
//            lz[x]--;
////            push(x , l != r);
//            return;
//        }
//        int mid = l + r >> 1;
//        if(mid >= pos)update(x * 2 , l , mid , pos);
//        else update(x * 2 + 1 , mid + 1 , r , pos);
////        push(x * 2 , l != mid);
////        push(x * 2 + 1 , mid + 1 != r);
//        s[x] = min(s[x * 2] , s[x * 2 + 1]);
//    }
    void update(int x , int l , int r , int pos , int val){
//        push(x , l != r);
        if(l == r){
            if(l == pos)s[x] = val;
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos)update(x * 2 , l , mid , pos , val);
        else update(x * 2 + 1 , mid + 1 , r , pos , val);
//        push(x * 2 , l != mid);
//        push(x * 2 + 1 , mid + 1 != r);
        s[x] = min(s[x * 2] , s[x * 2 + 1]);
    }
    int query(int x , int l , int r , int L , int R){
//        push(x , l != r);
        if(l > R || L > r){
            return 1e9;
        }
        if(L <= l && r <= R){
            return s[x];
        }
        int mid = l + r >> 1;
        return min(query(x * 2 , l , mid , L , R) , query(x * 2 + 1 , mid + 1 , r , L , R));
    }
}s;
int top[12];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> a;
    for(int i = 1 ; i <= n ; ++i)cin >> d[i];
    for(int i = 1 ; i <= n ; ++i)d[i] = n - d[i] + 1;
//    for(int i = 1 ; i <= n ; ++i)cout << d[i] << " ";cout << endl;
    for(int i = 1 ; i <= n ; ++i){
        if(d[i] <= 10)top[d[i]] = i;
    }
    s.build(1 , 1 , n);
    cin >> q;
    while(q--){
        char type;cin >> type;
        if(type == 'E'){
            int i , e;cin >> i >> e;
            int now = 11;
            for(int j = 10 ; j >= 1 ; --j){
                if(top[j] == i){
                    now = j;
                }
            }
            for(int j = now ; j > e ; --j){
                top[j] = top[j - 1];
            }
            d[i] = d[top[e]];
            top[e] = i;
            for(int j = 1 ; j <= e ; ++j){
                s.update(1 , 1 , n , top[j] , --d[top[j]]);
            }
//            for(int j = 1 ; j <= n ; ++j){
//                cout << d[j] << " \n"[j == n];
//            }
        }else{
            int i;cin >> i;
            if(i == a){
                cout << 0 << '\n';
            }else if(i < a){
                int res = 0;
                int need = s.query(1 , 1 , n ,  i , a - 1);
                for(int i = 17 ; i >= 0 ; --i){
                    if(a + res + (1 << i) <= n && s.query(1 , 1 , n , a + res + 1 , a + res + (1 << i)) > need)
                        res += (1 << i);
                }
                cout << res + a - i << '\n';
            }else{
                int res = 0;
                int need = s.query(1 , 1 , n ,  a + 1 , i);
                for(int i = 17 ; i >= 0 ; --i){
                    if(a - res - (1 << i) >= 1 && s.query(1 , 1 , n , a - res - (1 << i) , a - res - 1) > need)
                        res += (1 << i);
                }
                cout << res + i - a << '\n';
            }
        }
    }
}

Compilation message (stderr)

cake.cpp: In member function 'void IT::build(int, int, int)':
cake.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
cake.cpp: In member function 'void IT::update(int, int, int, int, int)':
cake.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
cake.cpp: In member function 'int IT::query(int, int, int, int, int)':
cake.cpp:77:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:88:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50