oj.uz

답안 #697696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697696 2023-02-10T18:21:03 Z Do_you_copy 케이크 (CEOI14_cake) C++17
100 / 100
 888 ms 18600 KB 
//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;
        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;
    while (q--){
        char c;
        int i, e; cin >> c;
        if (c == 'E'){
            cin >> i >> e;
            S.erase(S.find(make_pair(a[i], i)));
            vector <int> V;
            while (--e){
                V.pb(S.begin()->se);
                S.erase(S.begin());
            }
            int cnt = S.size() ? S.begin()->fi : 0;
            V.pb(i);
            reverse(V.begin(), V.end());
            for (int j: V){
                a[j] = ++cnt;
                st.update(1, j, a[j], 1, n);
                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

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 5 ms 4308 KB Output is correct
5 Correct 14 ms 4692 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 421 ms 4692 KB Output is correct
2 Correct 237 ms 4764 KB Output is correct
3 Correct 258 ms 4736 KB Output is correct
4 Correct 162 ms 4692 KB Output is correct
5 Correct 433 ms 5468 KB Output is correct
6 Correct 357 ms 5580 KB Output is correct
7 Correct 301 ms 5500 KB Output is correct
8 Correct 205 ms 5500 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 9848 KB Output is correct
2 Correct 74 ms 9700 KB Output is correct
3 Correct 69 ms 9624 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 210 ms 17520 KB Output is correct
6 Correct 189 ms 17612 KB Output is correct
7 Correct 120 ms 17280 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4416 KB Output is correct
2 Correct 32 ms 4564 KB Output is correct
3 Correct 84 ms 6948 KB Output is correct
4 Correct 89 ms 6992 KB Output is correct
5 Correct 116 ms 4556 KB Output is correct
6 Correct 142 ms 8064 KB Output is correct
7 Correct 120 ms 5216 KB Output is correct
8 Correct 183 ms 9332 KB Output is correct
9 Correct 888 ms 18580 KB Output is correct
10 Correct 379 ms 5384 KB Output is correct
11 Correct 500 ms 6528 KB Output is correct
12 Correct 826 ms 15904 KB Output is correct
13 Correct 601 ms 18600 KB Output is correct