Submission #825152

#	Time	Username	Problem	Language	Result	Execution time	Memory
825152		alvingogo	Radio Towers (IOI22_towers)	C++17	23 / 100	4099 ms	8116 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<int> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int p,int k){
        if(L==R){
            st[v]=k;
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,k);
        }
        else{
            update(2*v+2,m+1,R,p,k);
        }
        st[v]=max(st[2*v+1],st[2*v+2]);
    }
    int query(int v,int L,int R,int l,int r){
        if(l>r){
            return 0;
        }
        if(L==l && r==R){
            return st[v];
        }
        int m=(L+R)/2;
        if(r<=m){
            return query(2*v+1,L,m,l,r);
        }
        else if(l>m){
            return query(2*v+2,m+1,R,l,r);
        }
        else{
            return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
        }
    }
};
vector<int> v;
int mx;
int n;
void init(int N, vector<int> h) {
    v=h;
    n=N;
}

int max_towers(int l, int r, int d) {
    ST st;
    st.init(n);
    vector<int> a(n,l);
    set<pair<int,int> > s;
    for(int i=r;i>=l;i--){
        while(s.size()){
            auto h=*s.begin();
            if(h.fs+d<=v[i]){
                a[h.sc]=i;
                s.erase(h);
            }
            else{
                break;
            }
        }
        s.insert({v[i],i});
    }
    vector<int> dp(n);
    s.clear();
    int ans=0;
    for(int i=l;i<=r;i++){
        while(s.size()){
            auto h=*s.begin();
            if(h.fs+d<=v[i]){
                st.update(0,0,n-1,h.sc,dp[h.sc]);
                s.erase(h);
            }
            else{
                break;
            }
        }
        dp[i]=st.query(0,0,n-1,l,a[i]-1)+1;
        s.insert({v[i],i});
        ans=max(ans,dp[i]);
    }
    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