oj.uz

Submission #140631

# Submission time Handle Problem Language Result Execution time Memory
140631 2019-08-03T22:35:49 Z silxikys Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 8052 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

/*
 * fast queries (few updates): 
 *      after each update, simply recompute all orders and 
 *      queries in O(1)
 *
 * fast updates (few queries):
 *      Give everyone enough space initally (5e5,2*5e5,3*5e5,...,10*5e5,10*5e5+1)
 *      Save each update, then before each query, recompute all orders and
 *      answer the query.
*/

const int maxn = 250005;
const int maxq = 5e5+5;
const ll INF = 1LL<<62;
int N, Q;
int d[maxn];
ll a[maxn];
int start;
int ans[maxn];
vector<int> v;

int ord[maxn];

void calcans() {
    int t = 0;
    int l = start, r = start;
    while (l != 1 || r != N) {
        if (l == 1) {
            ans[r+1] = t;
            r++;
        }
        else if (r == N) {
            ans[l-1] = t;
            l--;
        }
        else {
            if (ord[l-1] > ord[r+1]) {
                ans[l-1] = t;
                l--;
            }
            else {
                ans[r+1] = t;
                r++;
            }
        }
        t++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> start;
    vector<pair<int,int>> ps;
    for (int i = 1; i <= N; i++) {
        cin >> d[i];
        ps.push_back({d[i],i});
    }
    sort(ps.begin(),ps.end(),greater<pair<int,int>>());
    int t = 0;
    multiset<ll> ms;
    for (auto p: ps) {
        v.push_back(p.second);
        ord[p.second] = t;
        t++;
    }

    calcans();

    cin >> Q;
    while (Q--) {
        char c; cin >> c;
        if (c == 'E') { //update
            int i, e; cin >> i >> e;
            v.erase(find(v.begin(),v.end(),i));
            v.insert(v.begin()+e-1,i);

            for (int t = 0; t < v.size(); t++) {
                ord[v[t]] = t;
            }
            calcans();
        }
        else { //query
            int b; cin >> b;
            cout << ans[b] << '\n';
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:82:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int t = 0; t < v.size(); t++) {
                             ~~^~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 632 KB Time limit exceeded
2 Execution timed out 2064 ms 632 KB Time limit exceeded
3 Execution timed out 2072 ms 760 KB Time limit exceeded
4 Execution timed out 2049 ms 632 KB Time limit exceeded
5 Execution timed out 2045 ms 1144 KB Time limit exceeded
6 Execution timed out 2073 ms 1144 KB Time limit exceeded
7 Execution timed out 2077 ms 1144 KB Time limit exceeded
8 Execution timed out 2080 ms 1144 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 3824 KB Output isn't correct
2 Incorrect 83 ms 3820 KB Output isn't correct
3 Incorrect 81 ms 3696 KB Output isn't correct
4 Incorrect 2 ms 380 KB Output isn't correct
5 Incorrect 178 ms 7912 KB Output isn't correct
6 Incorrect 195 ms 8052 KB Output isn't correct
7 Incorrect 162 ms 7656 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 628 KB Output isn't correct
2 Incorrect 552 ms 896 KB Output isn't correct
3 Execution timed out 2062 ms 2032 KB Time limit exceeded
4 Execution timed out 2071 ms 2048 KB Time limit exceeded
5 Incorrect 666 ms 872 KB Output isn't correct
6 Execution timed out 2071 ms 2672 KB Time limit exceeded
7 Execution timed out 2068 ms 1052 KB Time limit exceeded
8 Execution timed out 2083 ms 3308 KB Time limit exceeded
9 Execution timed out 2082 ms 7440 KB Time limit exceeded
10 Execution timed out 2082 ms 1508 KB Time limit exceeded
11 Execution timed out 2088 ms 1148 KB Time limit exceeded
12 Execution timed out 2062 ms 6224 KB Time limit exceeded
13 Execution timed out 2080 ms 7344 KB Time limit exceeded