Submission #651439

#	Time	Username	Problem	Language	Result	Execution time	Memory
651439		Lobo	Radio Towers (IOI22_towers)	C++17	23 / 100	4099 ms	13728 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second

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];

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]);
    }
}

// binary search left, find the more to the left <= x
int bsl(int l, int r, int x) {
    int ans;
    while(l <= r) {
        int mid = (l+r)/2;
        if(qrmn(1,0,n-1,l,mid).fr <= x) {
            ans = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    return ans;
}
int bsr(int l, int r, int x) {
    int ans;
    while(l <= r) {
        int mid = (l+r)/2;
        if(qrmn(1,0,n-1,mid,r).fr <= x) {
            ans = mid;
            l = mid+1;
        }
        else {
            r = mid-1;
        }
    }
    return ans;
}

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);
        if(ansl == 0) {
            for(int j = l; j <= i-1; j++) {
                if(a[j] <= a[i]-d) {
                    atvl[j] = 1;
                    break;
                }
            }
            for(int j = i-1; j >= l; j--) {
                if(a[j] <= a[i]-d) {
                    atvr[j] = 1;
                    break;
                }
            }
        }

        // 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);
        if(ansr == 0) {
            for(int j = i+1; j <= r; j++) {
                if(a[j] <= a[i]-d) {
                    atvl[j] = 1;
                    break;
                }
            }
            for(int j = r; j >= i+1; j--) {
                if(a[j] <= a[i]-d) {
                    atvr[j] = 1;
                    break;
                }
            }
        }
    }
    // 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;
    sol(L,R,D);
    pf[0] = atvl[0];
    for(int i = 1; i < n; i++) pf[i] = pf[i-1]+atvl[i];
    return max(1,pf[R]-(L==0 ? 0 : pf[L-1]));
}

Compilation message (stderr)

towers.cpp: In function 'int bsl(int, int, int)':
towers.cpp:61:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     return ans;
      |            ^~~
towers.cpp: In function 'int bsr(int, int, int)':
towers.cpp:75:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     return ans;
      |            ^~~

• 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