Submission #697691

#	Time	Username	Problem	Language	Result	Execution time	Memory
697691		Do_you_copy	Cake (CEOI14_cake)	C++17	0 / 100	2100 ms	22028 KiB

cake

//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 250004 + 1;
//const int Mod = 1e9 + 7;
//const int inf =
int n, A;
int a[maxN];

bool found;
struct TST{
    int st[maxN * 4];
    TST(){
        memset(st, 0, sizeof(st));
    }
    void update(int id, int i, int x, int l, int r){
        if (l == r){
            st[id] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if (i <= mid) update(id << 1, i, x, l, mid);
        else update(id << 1 | 1, i, x, mid + 1, r);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    int getmax(int id, int i, int j, int l, int r){
        if (i > r || l > j) return 0;
        if (i <= l && r <= j) return st[id];
        int mid = (l + r) >> 1;
        return max(getmax(id << 1, i, j, l, mid), getmax(id << 1 | 1, i, j, mid + 1, r));
    }
    int find(int id, int i, int j, int x, int t, int l, int r){
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (t){
            if (st[id << 1 | 1] > x) return find(id << 1 | 1, i, j, x, t, mid + 1, r);
            else return find(id << 1, i, j, x, t, l, mid);
        }
        else{
            if (st[id << 1] > x) return find(id << 1, i, j, x, t, l, mid);
            else return find(id << 1 | 1, i, j, x, t, mid + 1, r);
        }

    }
    int get(int id, int i, int j, int x, bool t, int l, int r){
        if (i > r || l > j) return t ? 0 : n + 1;
        cerr << i << " " << j << " " << t << " " << l << " " << r << "\n";
        if (i <= l && r <= j){
            if (st[id] < x || found) return t ? 0 : n + 1;
            found = 1;
            return find(id, i, j, x, t, l, r);
        }
        if (st[id] < x || found) return t ? 0 : n + 1;
        int mid = (l + r) >> 1;
        if (t){
            int fi = get(id << 1 | 1, i, j, x, t, mid + 1, r);
            int se = get(id << 1, i, j, x, t, l, mid);
            return max(fi, se);
        }
        else{
            int fi = get(id << 1, i, j, x, t, l, mid);
            int se = get(id << 1 | 1, i, j, x, t, mid + 1, r);
            return min(fi, se);
        }
    }
};
TST st;
void Init(){
    cin >> n >> A;
    set <pii, greater <pii>> S;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        S.insert({a[i], i});
    }
    for (int i = 1; i <= n; ++i){
        st.update(1, i, a[i], 1, n);
    }
    int q; cin >> q;
    int cur = n;
    while (q--){
        char c;
        int i, e; cin >> c;
        if (c == 'E'){
            cin >> i >> e;
            S.erase(S.find(make_pair(a[i], i)));
            ++cur;
            a[i] = cur - e + 1;
            st.update(1, i, a[i], 1, n);
            vector <int> V;
            while (--e){
                V.pb(S.begin()->se);
                S.erase(S.begin());
            }
            for (int j: V){
                ++a[j];
                st.update(1, j, a[j], 1, n);
            }
            S.insert(make_pair(a[i], i));
            for (int j: V) S.insert(make_pair(a[j], j));
        }
        else{
            cin >> i;
            found = 0;
            if (i > A){
                int maxx = st.getmax(1, A + 1, i, 1, n);
                int pos = st.get(1, 1, A - 1, maxx, 1, 1, n);
                cout << i - pos - 1<< "\n";
            }
            else if (i < A){
                int maxx = st.getmax(1, i, A - 1, 1, n);
                int pos = st.get(1, A + 1, n, maxx, 0, 1, n);
                cout << pos - i - 1<< "\n";
            }
            else{
                cout << 0 << "\n";
            }
        }
    }

}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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