oj.uz

Submission #153405

# Submission time Handle Problem Language Result Execution time Memory
153405 2019-09-14T06:01:32 Z Mercenary Cake (CEOI14_cake) C++14
0 / 100
 1424 ms 15660 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] , lz[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);
        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;
//            cout << l << " " << pos << " " << s[x] << endl;
            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);
        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){
//            cout << l << " " << r << " " << s[x] << endl;
            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));
    }
}l , r;
int top[11];

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;
    }
    l.build(1 , 1 , a - 1);
    r.build(1 , a + 1 , n);
    cin >> q;
    while(q--){
        char type;cin >> type;
        if(type == 'E'){
            int i , e;cin >> i >> e;
            l.lz[1]++;
            r.lz[1]++;
            int now = 10;
            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];
            }
            for(int j = 1 ; j < e ; ++j){
                if(top[j] < a)l.update(1 , 1 , a - 1 , top[j]);
                else r.update(1 , a + 1 , n , top[j]);
            }
            top[e] = i;
            if(i < a)l.update(1 , 1 , a - 1 , i , e);
            else if(i > a)r.update(1 , a + 1 , n , i , e);
//            for(int j = 1 ; j <= 10 ; ++j){
//                cerr << top[j] << " \n"[j == 10];
//            }
        }else{
            int i;cin >> i;
            if(i == a){
                cout << 0 << '\n';
            }else if(i < a){
                int res = 0;
                int need = l.query(1 , 1 , a - 1 ,  i , a - 1);
//                cerr << need << endl;
                for(int i = 17 ; i >= 0 ; --i){
                    if(a + res + (1 << i) <= n && r.query(1 , a + 1 , n , a + res + 1 , a + res + (1 << i)) > need)
                        res += (1 << i);
                }
                cout << res + a - i << '\n';
            }else{
                int res = 0;
                int need = r.query(1 , a + 1 , n ,  a + 1 , i);
//                cerr << need << endl;
                for(int i = 17 ; i >= 0 ; --i){
                    if(a - res - (1 << i) >= 1 && l.query(1 , 1 , a - 1 , 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)':
cake.cpp:49: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:61: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:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
cake.cpp: In function 'int main()':
cake.cpp:87: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:88: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 4964 KB Output isn't correct
2 Incorrect 171 ms 5112 KB Output isn't correct
3 Incorrect 192 ms 5112 KB Output isn't correct
4 Correct 134 ms 5112 KB Output is correct
5 Incorrect 266 ms 5624 KB Output isn't correct
6 Incorrect 244 ms 6000 KB Output isn't correct
7 Incorrect 207 ms 5880 KB Output isn't correct
8 Correct 149 ms 6008 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 4796 KB Output is correct
2 Incorrect 258 ms 4600 KB Output isn't correct
3 Incorrect 275 ms 4728 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 395 ms 8564 KB Output is correct
6 Incorrect 329 ms 8568 KB Output isn't correct
7 Incorrect 400 ms 8300 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 948 KB Output isn't correct
2 Incorrect 76 ms 968 KB Output isn't correct
3 Incorrect 171 ms 2704 KB Output isn't correct
4 Incorrect 174 ms 2936 KB Output isn't correct
5 Incorrect 179 ms 1844 KB Output isn't correct
6 Incorrect 268 ms 4344 KB Output isn't correct
7 Incorrect 237 ms 2936 KB Output isn't correct
8 Incorrect 116 ms 5368 KB Output isn't correct
9 Incorrect 1424 ms 13484 KB Output isn't correct
10 Incorrect 571 ms 5260 KB Output isn't correct
11 Incorrect 754 ms 6648 KB Output isn't correct
12 Incorrect 1382 ms 12888 KB Output isn't correct
13 Incorrect 1181 ms 15660 KB Output isn't correct