oj.uz

Submission #471014

# Submission time Handle Problem Language Result Execution time Memory
471014 2021-09-06T16:07:20 Z AmirElarbi Cake (CEOI14_cake) C++14
10 / 100
 2000 ms 4172 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define fi first
#define se second
#define INF 1e7
#define unsigned u
#define eps 1e-18
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 100005;
vi s;int n;
int tree[1000000];
int mrg(int a, int b)
{
    return max(a,b);
}
void build(int v = 1, int i = 0, int j = n-1){
    if(i == j){
       tree[v] = s[i];
       return;
    }
    int md = (i+j)/2;
    build(v*2, i, md);
    build(v*2+1, md+1, j);  
    tree[v] = mrg(tree[v*2],tree[v*2+1]);
}
int query(int v, int i, int j, int x , int y){
    if(j < x || i > y)
        return 0;
    if(i >= x && j <= y){
        return tree[v]; 
    }
    int md = (i+j)/2;
    int a = query(v*2, i, md, x, y), b = query(v*2+1, md+1, j, x, y);
    return mrg(a,b);
}
int get_first(int v, int lv, int rv, int l, int r, int x, bool k) {
    if(lv > r || rv < l) return -1;
    if(l <= lv && rv <= r) {
        if(tree[v] <= x) return -1;
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(k){
                if(tree[2*v] > x) {
                    v = 2*v;
                    rv = mid;
                }else {
                    v = 2*v+1;
                    lv = mid+1;
                }
            } else {
                if(tree[2*v+1] > x) {
                    v = 2*v+1;
                    lv = mid+1;
                }else {
                    v = 2*v;
                    rv = mid;
                }
            }
        }
        return lv;
    }

    int mid = lv + (rv-lv)/2;
    if(k){
        int rs = get_first(2*v, lv, mid, l, r, x,k);
        if(rs != -1) return rs;
        return get_first(2*v+1, mid+1, rv, l ,r, x,k);
    } else {
        int rs = get_first(2*v+1, mid+1, rv, l ,r, x,k);
        if(rs != -1) return rs;
        return get_first(2*v, lv, mid, l, r, x,k);
    }
}
void upd(int v, int i, int j, int pos, int value, bool k){
    if(j < pos || i > pos)
        return;
    if(i == j){
       if(k){
           tree[v] = value;
           s[pos] = value;
       } else {
            tree[v] += value;
           s[pos] += value;
       }
       return;
    }
    int md = (i+j)/2;
    upd(v*2, i, md, pos, value,k);
    upd(v*2+1, md+1, j, pos, value,k);
    tree[v] = mrg(tree[v*2],tree[v*2+1]);
} 
int main() { 
    optimise;
    int start;
    cin >> n >> start;
    start--;
    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        s.pb(a);
    }
    build();
    int q;
    cin >> q;
    while(q--){
        char be;
        cin >> be;
        if(be == 'F'){
            int a;
            cin >> a;
            a--;
            if(start > a){
                int mx = query(1,0,n-1,a,start-1);
                int lim = get_first(1,0,n-1,start+1, n-1,mx,1);
                if(lim == -1) lim = n;
                cout << lim - a -1 << endl;
            } else if(a == start){
                cout << 0 << endl;
            } else {
                int mx = query(1,0,n-1,start+1,a);
                int lim = get_first(1,0,n-1,0,start-1,mx,0);
                cout << a - lim - 1  << endl;
            }
        } else {
            int a,b;
            cin >> a >> b;
            a--;
            b = n-b+1;
            for (int i = 0; i < n; ++i)
            {
                if(s[i] <= b && s[i]>s[a])
                    upd(1,0,n-1,i,-1,0);
            }
            upd(1,0,n-1,a,b,1);
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 187 ms 332 KB Output is correct
5 Execution timed out 2082 ms 548 KB Time limit exceeded

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 536 KB Time limit exceeded
2 Execution timed out 2099 ms 460 KB Time limit exceeded
3 Execution timed out 2097 ms 536 KB Time limit exceeded
4 Execution timed out 2088 ms 548 KB Time limit exceeded
5 Execution timed out 2097 ms 716 KB Time limit exceeded
6 Execution timed out 2080 ms 788 KB Time limit exceeded
7 Execution timed out 2092 ms 716 KB Time limit exceeded
8 Execution timed out 2087 ms 716 KB Time limit exceeded

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1652 ms 2560 KB Output is correct
2 Correct 844 ms 2344 KB Output is correct
3 Correct 363 ms 2340 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Execution timed out 2078 ms 4068 KB Time limit exceeded
6 Correct 1769 ms 4172 KB Output is correct
7 Correct 256 ms 3908 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 404 KB Time limit exceeded
2 Execution timed out 2062 ms 436 KB Time limit exceeded
3 Execution timed out 2091 ms 1104 KB Time limit exceeded
4 Execution timed out 2094 ms 1104 KB Time limit exceeded
5 Execution timed out 2075 ms 380 KB Time limit exceeded
6 Execution timed out 2088 ms 1180 KB Time limit exceeded
7 Execution timed out 2070 ms 556 KB Time limit exceeded
8 Execution timed out 2086 ms 1868 KB Time limit exceeded
9 Execution timed out 2077 ms 3388 KB Time limit exceeded
10 Execution timed out 2086 ms 760 KB Time limit exceeded
11 Execution timed out 2087 ms 796 KB Time limit exceeded
12 Execution timed out 2083 ms 3184 KB Time limit exceeded
13 Execution timed out 2088 ms 3452 KB Time limit exceeded