Submission #651462

#	Time	Username	Problem	Language	Result	Execution time	Memory
651462		Lobo	Radio Towers (IOI22_towers)	C++17	23 / 100	4096 ms	88588 KiB

towers

#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(L,R,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
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23