oj.uz

Submission #791884

# Submission time Handle Problem Language Result Execution time Memory
791884 2023-07-24T12:09:22 Z Trent Growing Trees (BOI11_grow) C++17
0 / 100
 1000 ms 760 KB 
#include "bits/stdc++.h"

using namespace std;
#define forR(i, a) for(int i=0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i=(a); (i) < (b); ++(i))
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define all(a) (a).begin(), (a).end()
typedef long long ll;

const int MN = 1e5 + 10, ME = 4 * MN, INF=1e8;
int a[MN];
int las(int v, int nl, int nr, int val){
    for(int i=nr; i >= 0; --i) if(a[i] < val) return i;
}
int val(int v, int nl, int nr, int i){
    return a[i];
}
void upd(int v, int nl, int nr, int l, int r){
    REP(i, l, r+1) a[i] += 1;
}
void build(int v, int nl, int nr){}

signed main(){
    int n, m; cin >> n >> m;
    REP(i, 1, n + 1) cin >> a[i];
    sort(a+1, a+n+1);
    a[0] = -INF;
    build(1,0,n);
    forR(g, m){
        char ins; int p, q;
        cin >> ins >> p >> q;
        if(ins == 'F'){
            int st=las(1,0,n,q)+1;
            int fi=min(n, st+p-1);
            int fv=val(1,0,n,fi);
            int j=las(1,0,n,fv);
            // take st...j
            int ex = fi-j;
            int en=las(1,0,n,fv+1);
            // take en-ex+1...en
            upd(1,0,n,st,j);
            upd(1,0,n,en-ex+1,en);
        } else {
            int lef=las(1, 0, n, p)+1, rig=las(1,0,n, q+1);
            cout << rig - lef + 1 << '\n';
        }
        // REP(i, 1, n + 1) cout << val(1,0,n,i) << ' ';
        // cout << '\n';
    }
}

Compilation message

grow.cpp: In function 'int las(int, int, int, int)':
grow.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
   15 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 212 KB Output is correct
2 Correct 8 ms 316 KB Output is correct
3 Correct 8 ms 212 KB Output is correct
4 Correct 6 ms 212 KB Output is correct
5 Correct 276 ms 492 KB Output is correct
6 Incorrect 380 ms 620 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 748 KB Time limit exceeded
2 Halted 0 ms 0 KB -