oj.uz

Submission #651461

# Submission time Handle Problem Language Result Execution time Memory
651461 2022-10-18T21:21:42 Z Lobo Radio Towers (IOI22_towers) C++17
11 / 100
 4000 ms 116340 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 hant) {
    int i = qrmx(1,0,n-1,l,r).sc;
    int ans = 0;
    int ansl=0,ansr=0;
    if(i != l && qrmn(1,0,n-1,l,i-1).fr <= a[i]-d) {
        ansl = sol(l,i-1,d,a[i]);
        ans+= max(ansl,1);
        if(ansl == 0) {
            ansl = 1;
            // procuro do l ate o i-1 pelos que dao certo
            atvs.pb({});
            for(int j = l; j <= i-1; j++) {
                atvs.back().pb(j);
            }
        }
    }
    int szbf = atvs.size(); // se quiser acesar o primeiro de ansr da pra ver o atvs[szbf]
    if(i != r && qrmn(1,0,n-1,i+1,r).fr <= a[i]-d) {
        ansr = sol(i+1,r,d,a[i]);
        ans+= max(ansr,1);
        if(ansr == 0) {
            ansr = 1;
            // procuro do i+1 ate o r pelos que dao certo
            atvs.pb({});
            for(int j = i+1; j <= r; j++) {
                atvs.back().pb(j);
            }
        }
    }
    if(ansl != 0 && ansr == 0) {
        // eu posso pegar somente o i e nao pegar os caras em ansl
        // falo que da pra pegar o i colocando ele no ultimo de ansl
        if(a[i] <= hant-d) atvs.back().pb(i);
    }
    if(ansl == 0 && ansr != 0) {
        // falo que da pra pegar o i colocando ele no primeiro de ansr
        if(a[i] <= hant-d) atvs[szbf].pb(i); // coloca no final mas depois ajeita
    }

    // 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,inf);
    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 Execution timed out 4006 ms 53320 KB Time limit exceeded
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 336 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 3 ms 464 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 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 2 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 2 ms 336 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 2 ms 464 KB Output is correct
35 Correct 2 ms 592 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 336 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 3 ms 464 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 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 2 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 2 ms 336 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 2 ms 464 KB Output is correct
35 Correct 2 ms 592 KB Output is correct
36 Correct 49 ms 4612 KB Output is correct
37 Incorrect 53 ms 6576 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 4107 ms 116340 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 4009 ms 56184 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 336 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 720 KB Output is correct
15 Correct 2 ms 464 KB Output is correct
16 Correct 2 ms 464 KB Output is correct
17 Correct 2 ms 464 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 3 ms 464 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 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 2 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 2 ms 336 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 2 ms 464 KB Output is correct
35 Correct 2 ms 592 KB Output is correct
36 Correct 49 ms 4612 KB Output is correct
37 Incorrect 53 ms 6576 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 Execution timed out 4006 ms 53320 KB Time limit exceeded
2 Halted 0 ms 0 KB -