Submission #629450

#	Time	Username	Problem	Language	Result	Execution time	Memory
629450		jeff252	Radio Towers (IOI22_towers)	C++17	23 / 100	4073 ms	55100 KiB

towers

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+10],dp[N];
pair<int,int>num[N],pw[N],sorted[N];
vi g[N];
void upd(int ind,int x){
    for(ind+=SS;ind>0;ind>>=1) seg[ind]=max(seg[ind],x);
}
int Query(int a,int b){
    int res=0;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) res=max(res,seg[a+1]);
        if(b&1) res=max(res,seg[b-1]);
    }
    return res;
}
void cnt(int l,int r,int d){
    for(int i=1;i<=SS*2;i++) seg[i]=0;
    for(int i=l;i<=r;i++){
        sorted[i-l+1]={t[i],i};
        sorted[r-l+1+i-l+1]={t[i]+d,i+r};
    }
    sort(sorted+1,sorted+1+(r-l+1)*2);
    int wsk=0;
    for(int i=1;i<=(r-l+1)*2;i++){
        if(i==1 or sorted[i].fi!=sorted[i-1].fi) wsk++;
        if(sorted[i].se>r) num[sorted[i].se-r].se=wsk;
        else num[sorted[i].se].fi=wsk;
    }
    for(int i=l;i<=r;i++){
        pw[i].fi=Query(num[i].se,wsk);
        upd(num[i].fi,i);
    }
    for(int i=1;i<=SS*2;i++) seg[i]=0;
    for(int i=r;i>=l;i--){
        pw[i].se=Query(num[i].se,wsk);
        if(pw[i].se!=0) pw[i].se=r-pw[i].se+1;
        upd(num[i].fi,r-i+1);
    }
     for(int i=1;i<=SS*2;i++) seg[i]=0;
}
void init(int n,vi a){
    for(int i=0;i<n;i++) t[i+1]=a[i];
}
int max_towers(int l,int r,int d){
    l++,r++;
    cnt(l,r,d);
    int res=0;
    for(int i=l;i<=r;i++){
        if(pw[i].fi!=0) dp[i]=Query(l,pw[i].fi-1);
        dp[i]++;
        res=max(res,dp[i]);
        if(pw[i].se!=0) g[pw[i].se].push_back(i);
        for(auto u:g[i]) upd(u,dp[u]);
    }
    return res;
}
/*int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int n;
    cin>>n;
    vi xd;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        xd.push_back(a);
    }
    init(n,xd);
    int q;
    cin>>q;
    while(q--){
        int l,r,d;
        cin>>l>>r>>d;
        cout<<max_towers(l,r,d)<<"\n";
    }
}*/

• 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