oj.uz

Submission #651449

# Submission time Handle Problem Language Result Execution time Memory
651449 2022-10-18T19:02:01 Z Lobo Radio Towers (IOI22_towers) C++17
11 / 100
 4000 ms 2097152 KB 
#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()

const int maxn = 1e5+10;
const int inf = 1e9+10;

int n, a[maxn], atvl[maxn], atvr[maxn], pf[maxn];
pair<int,int> trmn[4*maxn], trmx[4*maxn];
vector<vector<int>> atvs;

void att(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trmn[no] = mp(val,pos);
        trmx[no] = mp(val,pos);
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)/2;
    att(f1,l,mid,pos,val);
    att(f2,mid+1,r,pos,val);
    trmn[no] = min(trmn[f1],trmn[f2]);
    trmx[no] = max(trmx[f1],trmx[f2]);
}
pair<int,int> qrmn(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return mp(inf,0);
    if(l >= L && r <= R) return trmn[no];
    int f1=2*no,f2=2*no+1,mid=(l+r)/2;
    return min(qrmn(f1,l,mid,L,R),qrmn(f2,mid+1,r,L,R));
}
pair<int,int> qrmx(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return mp(-inf,0);
    if(l >= L && r <= R) return trmx[no];
    int f1=2*no,f2=2*no+1,mid=(l+r)/2;
    return max(qrmx(f1,l,mid,L,R),qrmx(f2,mid+1,r,L,R));
}

void init(int N, vector<int> H) {
    n = N;
    for(int i = 0; i < n; i++) {
        a[i] = H[i];
        att(1,0,n-1,i,a[i]);
    }
}

int sol(int l, int r, int d) {
    int i = qrmx(1,0,n-1,l,r).sc;
    int ans = 0;
    if(i != l && qrmn(1,0,n-1,l,i-1).fr <= a[i]-d) {
        int ansl = sol(l,i-1,d);
        ans+= max(ansl,1);
        int idmn = qrmn(1,0,n-1,l,i-1).sc;
        if(ansl == 0) {
            atvs.pb({});
            atvs.back().pb(idmn);
            ansl = 1;
        }
        if(ansl == 1) {
            for(int j = l; j <= i-1; j++) {
                if(a[j] <= a[i]-d && j != idmn) {
                    atvs.back().pb(j);
                }
            }
            // sort(all(atvs.back()));
        }
        // more to the left and to the right that is <= a[i]-d
    }
    if(i != r && qrmn(1,0,n-1,i+1,r).fr <= a[i]-d) {
        int ansr = sol(i+1,r,d);
        ans+= max(ansr,1);
        int idmn = qrmn(1,0,n-1,i+1,r).sc;
        if(ansr == 0) {
            atvs.pb({});
            atvs.back().pb(idmn);
            ansr = 1;
        }
        if(ansr == 1) {
            for(int j = i+1; j <= r; j++) {
                if(a[j] <= a[i]-d && j != idmn) {
                    atvs.back().pb(j);
                }
            }
            // sort(all(atvs.back()));
        }
    }
    // if(i != l && qrmn(1,0,n-1,l,i-1).fr <= a[i]-d) ans+= max(1,sol(l,i-1,d));
    // if(i != r && qrmn(1,0,n-1,i+1,r).fr <= a[i]-d) ans+= max(1,sol(i+1,r,d));
    // cout << l << " " << r << " " << d << " " << ans << endl;
    return ans;
}

bool calc = false;
int max_towers(int L, int R, int D) {
    for(int i = 0; i < n; i++) atvl[i] = 0;
    for(int i = 0; i < n; i++) atvr[i] = 0;
    sol(0,n-1,D);
    int ans = 0;
    for(auto vc : atvs) {
        int ok = 0;
        for(auto x : vc) {
            if(L <= x && x <= R) ok = 1;
            // cout << x << " ";
        }
        // cout << endl;
        ans+= ok;
    }
    return max(1,ans);
    // pfl[0] = atvl[0];
    // pfr[0] = atvr[0];
    // for(int i = 1; i < n; i++) pfl[i] = pfl[i-1]+atvl[i];
    // for(int i = 1; i < n; i++) pfr[i] = pfr[i-1]+atvr[i];
    // return max(1,pf[R]-(L==0 ? 0 : pf[L-1]));
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 3655 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 5 ms 1352 KB Output is correct
9 Correct 20 ms 13164 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 16 ms 11964 KB Output is correct
14 Correct 23 ms 16432 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 23 ms 16340 KB Output is correct
19 Correct 9 ms 5692 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 23 ms 16440 KB Output is correct
24 Correct 3 ms 1352 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 3 ms 344 KB Output is correct
32 Correct 16 ms 7720 KB Output is correct
33 Correct 10 ms 4424 KB Output is correct
34 Correct 3 ms 848 KB Output is correct
35 Correct 2 ms 976 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 5 ms 1352 KB Output is correct
9 Correct 20 ms 13164 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 16 ms 11964 KB Output is correct
14 Correct 23 ms 16432 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 23 ms 16340 KB Output is correct
19 Correct 9 ms 5692 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 23 ms 16440 KB Output is correct
24 Correct 3 ms 1352 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 3 ms 344 KB Output is correct
32 Correct 16 ms 7720 KB Output is correct
33 Correct 10 ms 4424 KB Output is correct
34 Correct 3 ms 848 KB Output is correct
35 Correct 2 ms 976 KB Output is correct
36 Correct 54 ms 4684 KB Output is correct
37 Incorrect 53 ms 6432 KB 1st lines differ - on the 1st token, expected: '2946', found: '2945'
38 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 5 ms 1352 KB Output is correct
9 Correct 20 ms 13164 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 16 ms 11964 KB Output is correct
14 Correct 23 ms 16432 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 23 ms 16340 KB Output is correct
19 Correct 9 ms 5692 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 23 ms 16440 KB Output is correct
24 Correct 3 ms 1352 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 3 ms 344 KB Output is correct
32 Correct 16 ms 7720 KB Output is correct
33 Correct 10 ms 4424 KB Output is correct
34 Correct 3 ms 848 KB Output is correct
35 Correct 2 ms 976 KB Output is correct
36 Correct 54 ms 4684 KB Output is correct
37 Incorrect 53 ms 6432 KB 1st lines differ - on the 1st token, expected: '2946', found: '2945'
38 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3655 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -