oj.uz

Submission #471011

# Submission time Handle Problem Language Result Execution time Memory
471011 2021-09-06T15:58:56 Z AmirElarbi Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 4684 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, n-1,mx,1);
                if(lim == -1) lim = n-1;
                cout << lim - a << 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,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 Incorrect 1 ms 204 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 2075 ms 536 KB Time limit exceeded
2 Execution timed out 2064 ms 556 KB Time limit exceeded
3 Execution timed out 2073 ms 460 KB Time limit exceeded
4 Execution timed out 2064 ms 1312 KB Time limit exceeded
5 Execution timed out 2079 ms 716 KB Time limit exceeded
6 Execution timed out 2084 ms 716 KB Time limit exceeded
7 Execution timed out 2092 ms 788 KB Time limit exceeded
8 Execution timed out 2073 ms 1180 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1628 ms 2684 KB Output isn't correct
2 Incorrect 855 ms 2500 KB Output isn't correct
3 Incorrect 350 ms 2304 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Execution timed out 2072 ms 4532 KB Time limit exceeded
6 Incorrect 1725 ms 4684 KB Output isn't correct
7 Incorrect 251 ms 4284 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 516 KB Time limit exceeded
2 Execution timed out 2074 ms 564 KB Time limit exceeded
3 Execution timed out 2064 ms 1104 KB Time limit exceeded
4 Execution timed out 2082 ms 1104 KB Time limit exceeded
5 Execution timed out 2085 ms 580 KB Time limit exceeded
6 Execution timed out 2081 ms 1228 KB Time limit exceeded
7 Execution timed out 2080 ms 544 KB Time limit exceeded
8 Execution timed out 2091 ms 1988 KB Time limit exceeded
9 Execution timed out 2070 ms 3456 KB Time limit exceeded
10 Execution timed out 2078 ms 500 KB Time limit exceeded
11 Execution timed out 2084 ms 836 KB Time limit exceeded
12 Execution timed out 2087 ms 3272 KB Time limit exceeded
13 Execution timed out 2082 ms 3424 KB Time limit exceeded