oj.uz

Submission #153415

# Submission time Handle Problem Language Result Execution time Memory
153415 2019-09-14T06:50:40 Z Mercenary Cake (CEOI14_cake) C++14
100 / 100
 955 ms 5088 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 14 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 632 KB Output is correct
2 Correct 142 ms 568 KB Output is correct
3 Correct 162 ms 504 KB Output is correct
4 Correct 126 ms 632 KB Output is correct
5 Correct 233 ms 780 KB Output is correct
6 Correct 204 ms 632 KB Output is correct
7 Correct 179 ms 740 KB Output is correct
8 Correct 129 ms 760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 2404 KB Output is correct
2 Correct 187 ms 2276 KB Output is correct
3 Correct 168 ms 2212 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 246 ms 4088 KB Output is correct
6 Correct 212 ms 4092 KB Output is correct
7 Correct 226 ms 3832 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 520 KB Output is correct
2 Correct 51 ms 568 KB Output is correct
3 Correct 122 ms 1272 KB Output is correct
4 Correct 123 ms 1364 KB Output is correct
5 Correct 127 ms 760 KB Output is correct
6 Correct 190 ms 1620 KB Output is correct
7 Correct 172 ms 1016 KB Output is correct
8 Correct 99 ms 1784 KB Output is correct
9 Correct 955 ms 5088 KB Output is correct
10 Correct 422 ms 1592 KB Output is correct
11 Correct 539 ms 2016 KB Output is correct
12 Correct 924 ms 4920 KB Output is correct
13 Correct 774 ms 5052 KB Output is correct