Submission #634088

#	Time	Username	Problem	Language	Result	Execution time	Memory
634088		lis05st	Radio Towers (IOI22_towers)	C++17	0 / 100	4083 ms	379196 KiB

towers

//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include"towers.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

void precalc(){

}
#define MULTITESTS false
void solve(){

}


vector<int>val,pos;
int n;
vector<int>arr;

void build(int v,int l,int r){
    if(l==r){
        val[v]=arr[l];
        pos[v]=l;
        return;
    }
    int m=(l+r)/2;
    build(2*v,l,m);
    build(2*v+1,m+1,r);
    pos[v]=pos[2*v+1];
    val[v]=max(val[2*v],val[2*v+1]);
    if(val[2*v]>val[2*v+1])pos[v]=pos[2*v];
}

int get(int v,int l,int r,int l0,int r0){
    if(l==l0&&r==r0){
        return pos[v];
    }
    int m=(l+r)/2;
    if(r0<=m)return get(2*v,l,m,l0,r0);
    else if(l0>m)return get(2*v+1,m+1,r,l0,r0);
    int A=get(2*v,l,m,l0,m);
    int B=get(2*v+1,m+1,r,m+1,r0);
    int a=arr[A];
    int b=arr[B];
    return (a>b)?A:B;
}

void init(int N, std::vector<int> H){
    arr.swap(H);
    val.resize(4*N+5);
    pos.resize(4*N+5);
    n=N;
    build(1,0,n-1);
}
map<vector<int>,int>mp;
int solve(int L,int R,int D,int LIM=2e9+5){
    if(R<L)return 0;
    if(L==R){
        if(arr[L]<=LIM)return 1;
        return 0;
    }
    if(mp.count({L,R,D,LIM}))return mp[{L,R,D,LIM}];
    int p=get(1,0,n-1,L,R);
    int res=max({
        solve(L,p-1,D,LIM),
        solve(p+1,R,D,LIM),
        solve(L,p-1,D,min(LIM,arr[p]-D))+solve(p+1,R,D,min(LIM,arr[p]-D))
    });
    mp[{L,R,D,LIM}]=res;
    return res;
}
int max_towers(int L, int R, int D){
    return solve(L,R,D);
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23