oj.uz

답안 #95366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95366 2019-01-30T20:15:45 Z popovicirobert 케이크 (CEOI14_cake) C++14
0 / 100
 1456 ms 22748 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 250000;

int arr[MAXN + 1];

struct Data {
    int pos;
    bool operator <(const Data &other) const {
        return arr[pos] > arr[other.pos];
    }
};

multiset <Data> mst;

struct SegTree {
    vector < pair <int, int> > aint;
    int n;
    SegTree(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
        for(int i = 1; i <= 4 * n; i++) {
            aint[i] = {0, i};
        }
    }
    inline void refresh(int nod) {
        if(aint[2 * nod].first > aint[2 * nod + 1].first) {
            aint[nod] = aint[2 * nod];
        }
        else {
            aint[nod] = aint[2 * nod + 1];
        }
    }
    void build(int nod, int left, int right) {
        if(left == right) {
            aint[nod] = {arr[left], left};
        }
        else {
            int mid = (left + right) / 2;
            build(2 * nod, left, mid);
            build(2 * nod + 1, mid + 1, right);
            refresh(nod);
        }
    }
    void update(int nod, int left, int right, int pos, int val) {
        if(left == right) {
            aint[nod] = {val, left};
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
            refresh(nod);
        }
    }
    pair <int, int> query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod];
        }
        else {
            int mid = (left + right) / 2;
            pair <int, int> a, b;
            a = b = {0, 0};
            if(l <= mid) a = query(2 * nod, left, mid, l, r);
            if(mid < r) b = query(2 * nod + 1, mid + 1, right, l, r);
            if(a.first < b.first) {
                return b;
            }
            return a;
        }
    }
    int get_left(int nod, int left, int right, int pos, int val) {
        if(left > pos) {
            return 0;
        }
        if(right <= pos) {
            if(aint[nod].first > val) {
                return aint[nod].second;
            }
            return 0;
        }
        else {
            int mid = (left + right) / 2;
            int a = get_left(2 * nod, left, mid, pos, val), b = get_left(2 * nod + 1, mid + 1, right, pos, val);
            return max(a, b);
        }
    }
    int get_right(int nod, int left, int right, int pos, int val) {
        if(right < pos) {
            return n + 1;
        }
        if(left >= pos) {
            if(aint[nod].first > val) {
                return aint[nod].second;
            }
            return n + 1;
        }
        else {
            int mid = (left + right) / 2;
            int a = get_right(2 * nod, left, mid, pos, val), b = get_right(2 * nod + 1, mid + 1, right, pos, val);
            return min(a, b);
        }
    }
};


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, q, a;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> a;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
        mst.insert({i});
    }
    SegTree st(n);
    st.build(1, 1, n);
    cin >> q;
    while(q > 0) {
        q--;
        int pos, e;
        char ch;
        cin >> ch;
        if(ch == 'F') {
            cin >> pos;
            int ans = 0;
            if(a < pos) {
                ans = pos - st.get_left(1, 1, n, a - 1, st.query(1, 1, n, a + 1, pos).first) - 1;
            }
            else if(a > pos) {
                ans = st.get_right(1, 1, n, a + 1, st.query(1, 1, n, pos, a - 1).first) - pos - 1;
            }
            else if(a == pos) {
                ans = 0;
            }
            cout << ans << "\n";
        }
        else {
            cin >> pos >> e;
            auto it = mst.begin();
            int last = arr[it -> pos] + 1;
            int cnt = 0;
            while(cnt < e - 1 && it != mst.end()) {
                int cur = it -> pos;
                cnt += (cur != pos);
                it++;
                last = arr[cur];
                mst.erase(mst.find({cur}));
                arr[cur]++;
                mst.insert({cur});
            }
            mst.erase(mst.find({pos}));
            arr[pos] = last;
            mst.insert({pos});
            it = mst.begin();
            for(i = 0; i < e; i++) {
                st.update(1, 1, n, it -> pos, arr[it -> pos]);
                it++;
            }
            /*for(i = 1; i <= n; i++) {
                cerr << st.query(1, 1, n, i, i).first << " ";
            }
            cerr << "\n";*/
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 551 ms 1020 KB Output isn't correct
2 Correct 280 ms 1144 KB Output is correct
3 Incorrect 364 ms 1144 KB Output isn't correct
4 Correct 169 ms 1220 KB Output is correct
5 Incorrect 690 ms 2424 KB Output isn't correct
6 Incorrect 553 ms 2424 KB Output isn't correct
7 Incorrect 449 ms 2424 KB Output isn't correct
8 Correct 218 ms 2424 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 9208 KB Output isn't correct
2 Incorrect 80 ms 9028 KB Output isn't correct
3 Incorrect 71 ms 9052 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 354 ms 21576 KB Output isn't correct
6 Incorrect 329 ms 21624 KB Output isn't correct
7 Correct 126 ms 21400 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 632 KB Output isn't correct
2 Incorrect 39 ms 888 KB Output isn't correct
3 Incorrect 109 ms 4704 KB Output isn't correct
4 Incorrect 137 ms 4816 KB Output isn't correct
5 Incorrect 153 ms 832 KB Output isn't correct
6 Incorrect 217 ms 6368 KB Output isn't correct
7 Incorrect 163 ms 1656 KB Output isn't correct
8 Incorrect 329 ms 8740 KB Output isn't correct
9 Incorrect 1389 ms 22748 KB Output isn't correct
10 Incorrect 503 ms 1896 KB Output isn't correct
11 Incorrect 730 ms 3420 KB Output isn't correct
12 Incorrect 1456 ms 18552 KB Output isn't correct
13 Incorrect 1032 ms 22524 KB Output isn't correct