oj.uz

Submission #491692

# Submission time Handle Problem Language Result Execution time Memory
491692 2021-12-03T20:35:23 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 556 ms 8024 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <assert.h>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 500007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

priority_queue <int> pq;
int n, a, q, seg[4 * M], cur, pos[4 * M];

void upd(int i, int v, int node = 1, int l = 1, int r = n)
{
    if(l == r){
        seg[node] = v;
        return;
    }
    int mid = (l + r) / 2;
    if(i <= mid) upd(i, v, 2 * node, l, mid);
    else upd(i, v, 2 * node + 1, mid + 1, r);
    seg[node] = max(seg[2 * node], seg[2 * node + 1]);
    return;
}

int get(int st, int en, int node = 1, int l = 1, int r = n)
{
    if(l > en || r < st) return 0;
    if(l >= st && r <= en) return seg[node];
    int mid = (l + r) / 2;
    return max(get(st, en, 2 * node, l, mid), get(st, en, 2 * node + 1, mid + 1, r));
}

int findr(int st, int en, int v, int node = 1, int l = 1, int r = n)
{
    if(l > en || r < st || seg[node] < v) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = findr(st, en, v, 2 * node + 1, mid + 1, r);
    if(ret == -1) ret = findr(st, en, v, 2 * node, l, mid);
    return ret;
}

int findl(int st, int en, int v, int node = 1, int l = 1, int r = n)
{
    if(l > en || r < st || seg[node] < v) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = findl(st, en, v, 2 * node, l, mid);
    if(ret == -1) ret = findl(st, en, v, 2 * node + 1, mid + 1, r);
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> a;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        upd(i, x);
        pq.push(x);
        pos[x] = i;
    }
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'F'){
            int x;
            cin >> x;
            if(x == a) cout << 0 << endl;
            else if(a == 1 || a == n) cout << abs(a - x) << endl;
            else if(x > a){
                int res = get(a + 1, x), ans = x - a;
                int add = findr(1, a - 1, res);
                if(add == -1) add = 0;
                ans += a - add - 1;
                cout << ans << endl;
            }
            else{
                int res = get(x, a - 1), ans = a - x;
                int add = findl(a + 1, n, res);
                if(add == -1) add = n + 1;
                ans += add - a - 1;
                cout << ans << endl;
            }
        }
        else{
            int id, x;
            cin >> id >> x;
            vector <int> v;
            for(int i = 1; i < x; ++i){
                v.pb(pq.top());
                pq.pop();
            }
            int val = 1;
            if(pq.size()) val = pq.top() + 1;
            reverse(all(v));
            while(!v.empty()){
                int cur = v.back();
                int p = pos[cur];
                v.pop_back();
                pos[cur + 1] = p;
                upd(p, cur + 1);
                pq.push(cur + 1);
            }
            pq.push(val);
            pos[val] = id;
            upd(id, val);
//            map <int,int> vist;
//            for(int i = 1; i <= n; ++i){
//                assert(!vist[get(i, i)]);
//                cout << vist[get(i, i)] << " " ;
//                vist[get(i, i)] = 1;
//            }
//            cout << endl;
        }
    }
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 361 ms 4500 KB Output isn't correct
2 Correct 196 ms 4556 KB Output is correct
3 Correct 234 ms 4500 KB Output is correct
4 Correct 114 ms 4664 KB Output is correct
5 Incorrect 390 ms 4708 KB Output isn't correct
6 Incorrect 330 ms 6880 KB Output isn't correct
7 Correct 261 ms 7080 KB Output is correct
8 Correct 118 ms 6840 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2752 KB Output is correct
2 Incorrect 59 ms 2684 KB Output isn't correct
3 Correct 54 ms 2696 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Correct 102 ms 5112 KB Output is correct
6 Incorrect 97 ms 5028 KB Output isn't correct
7 Correct 87 ms 4796 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 712 KB Output isn't correct
2 Correct 26 ms 836 KB Output is correct
3 Correct 54 ms 1768 KB Output is correct
4 Incorrect 84 ms 1860 KB Output isn't correct
5 Incorrect 113 ms 1424 KB Output isn't correct
6 Correct 98 ms 2884 KB Output is correct
7 Correct 97 ms 1916 KB Output is correct
8 Correct 126 ms 4548 KB Output is correct
9 Incorrect 549 ms 8024 KB Output isn't correct
10 Incorrect 378 ms 3660 KB Output isn't correct
11 Incorrect 434 ms 5056 KB Output isn't correct
12 Correct 556 ms 7788 KB Output is correct
13 Incorrect 465 ms 8024 KB Output isn't correct