oj.uz

Submission #140632

# Submission time Handle Problem Language Result Execution time Memory
140632 2019-08-03T22:42:58 Z silxikys Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 8040 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 = 1;
    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();
    /*
    for (int i = 1; i <= N; i++) {
        cout << i << ": " << ans[i] << '\n';
    }
    */

    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:86:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int t = 0; t < v.size(); t++) {
                             ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 15 ms 504 KB Output is correct
5 Correct 216 ms 804 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 632 KB Time limit exceeded
2 Execution timed out 2055 ms 764 KB Time limit exceeded
3 Execution timed out 2062 ms 760 KB Time limit exceeded
4 Execution timed out 2056 ms 760 KB Time limit exceeded
5 Execution timed out 2051 ms 1148 KB Time limit exceeded
6 Execution timed out 2060 ms 1144 KB Time limit exceeded
7 Execution timed out 2064 ms 1140 KB Time limit exceeded
8 Execution timed out 2056 ms 1144 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3876 KB Output is correct
2 Correct 84 ms 3704 KB Output is correct
3 Correct 82 ms 3696 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 186 ms 8040 KB Output is correct
6 Correct 200 ms 7912 KB Output is correct
7 Correct 168 ms 7656 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 696 KB Output is correct
2 Correct 558 ms 760 KB Output is correct
3 Execution timed out 2053 ms 2136 KB Time limit exceeded
4 Execution timed out 2069 ms 2036 KB Time limit exceeded
5 Correct 675 ms 820 KB Output is correct
6 Execution timed out 2039 ms 2612 KB Time limit exceeded
7 Execution timed out 2070 ms 1016 KB Time limit exceeded
8 Execution timed out 2048 ms 3180 KB Time limit exceeded
9 Execution timed out 2037 ms 7428 KB Time limit exceeded
10 Execution timed out 2076 ms 1820 KB Time limit exceeded
11 Execution timed out 2017 ms 1144 KB Time limit exceeded
12 Execution timed out 2043 ms 6116 KB Time limit exceeded
13 Execution timed out 2056 ms 7428 KB Time limit exceeded