oj.uz

답안 #153412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153412 2019-09-14T06:37:08 Z Mercenary 케이크 (CEOI14_cake) C++14
0 / 100
 1562 ms 7236 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));
    }
}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;
            s.lz[1]++;
            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];
            }
            for(int j = 1 ; j < e ; ++j){
//                if(top[j] < a)l.update(1 , 1 , n , top[j]);
//                else r.update(1 , a + 1 , n , top[j]);
                s.update(1 , 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);
            s.update(1 , 1 , n , i , e);
//            cerr << e << " " << i << endl;
//            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 = s.query(1 , 1 , n ,  i , a - 1);
                for(int i = 17 ; i >= 0 ; --i){
                    if(a + res + (1 << i) <= n && s.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 = 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)':
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 243 ms 688 KB Output isn't correct
2 Incorrect 171 ms 692 KB Output isn't correct
3 Incorrect 191 ms 760 KB Output isn't correct
4 Incorrect 140 ms 700 KB Output isn't correct
5 Incorrect 281 ms 888 KB Output isn't correct
6 Incorrect 246 ms 888 KB Output isn't correct
7 Incorrect 214 ms 888 KB Output isn't correct
8 Incorrect 149 ms 1016 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 404 ms 3564 KB Output isn't correct
2 Incorrect 358 ms 3320 KB Output isn't correct
3 Incorrect 362 ms 3460 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 440 ms 6108 KB Output isn't correct
6 Incorrect 452 ms 6300 KB Output isn't correct
7 Incorrect 446 ms 6036 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 504 KB Output isn't correct
2 Incorrect 73 ms 776 KB Output isn't correct
3 Incorrect 168 ms 1784 KB Output isn't correct
4 Incorrect 189 ms 1788 KB Output isn't correct
5 Incorrect 189 ms 752 KB Output isn't correct
6 Incorrect 313 ms 2196 KB Output isn't correct
7 Incorrect 272 ms 1084 KB Output isn't correct
8 Incorrect 121 ms 2976 KB Output isn't correct
9 Incorrect 1562 ms 7236 KB Output isn't correct
10 Incorrect 616 ms 1624 KB Output isn't correct
11 Incorrect 859 ms 2440 KB Output isn't correct
12 Incorrect 1472 ms 6996 KB Output isn't correct
13 Incorrect 1317 ms 7208 KB Output isn't correct