oj.uz

Submission #651448

# Submission time Handle Problem Language Result Execution time Memory
651448 2022-10-18T19:00:42 Z Lobo Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 104120 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 Execution timed out 4073 ms 12796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 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 2 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 230 ms 1664 KB Output is correct
9 Execution timed out 4045 ms 4920 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 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 2 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 230 ms 1664 KB Output is correct
9 Execution timed out 4045 ms 4920 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4010 ms 104120 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 4038 ms 52704 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 336 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 2 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 230 ms 1664 KB Output is correct
9 Execution timed out 4045 ms 4920 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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