oj.uz

Submission #629413

# Submission time Handle Problem Language Result Execution time Memory
629413 2022-08-14T13:28:34 Z jeff252 Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 57192 KB 
#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-l+1)};
    }
    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-l+1) num[sorted[i].se-(r-l+1)].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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 45560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 27856 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 27856 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4049 ms 57192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4059 ms 40632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 27856 KB 1st lines differ - on the 1st token, expected: '13', found: '1'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 45560 KB Time limit exceeded
2 Halted 0 ms 0 KB -