Submission #344981

#	Time	Username	Problem	Language	Result	Execution time	Memory
344981		mehrdad_sohrabi	Holiday (IOI14_holiday)	C++14	100 / 100	4949 ms	32320 KiB

holiday

#include <bits/stdc++.h>
/// 500 485 462 A4
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e5+100;
ll seg[2][N*4];
ll ja[N];
ll a[N];
ll c[N];
ll dp[4][N];
ll n;
void upd(ll nod,ll l,ll r,ll id,ll di,ll val){
    if (r-l==1){
        seg[di][nod]+=val;
        if (di==0) if (seg[di][nod]<0 || seg[di][nod]>1) cout << "KOS" << endl;
        return ;
    }
    ll mid=(r+l)/2;
    if (mid>id) upd(nod*2,l,mid,id,di,val);
    else upd(nod*2+1,mid,r,id,di,val);
    seg[di][nod]=seg[di][nod*2]+seg[di][nod*2+1];
}
ll get(ll nod,ll l,ll r,ll L,ll R,ll id){
    if (l>=R || L>=r) return 0;
    if (l>=L && r<=R) return seg[id][nod];
    ll mid=(r+l)/2;
    return get(nod*2,l,mid,L,R,id)+get(nod*2+1,mid,r,L,R,id);
}
ll where(ll nod,ll l,ll r,ll k){
    if (r-l==1) return l;
    ll mid=(r+l)/2;
    if (seg[0][nod*2+1]>=k) return where(nod*2+1,mid,r,k);
    else return where(nod*2,l,mid,k-seg[0][nod*2+1]);
}
void solve(ll l,ll r,ll L,ll R,ll id){
    if (r<l) return ;
    ll mid=(r+l)/2;
    ll best=L,o=-1;
    for (int i=L;i<=min(mid,R);i++){
        upd(1,1,n+1,ja[i],0,1);
        upd(1,1,n+1,ja[i],1,a[i]);
        ll z=where(1,1,n+1,mid-i+1);
        ll h=get(1,1,n+1,z,n+1,0);
    //    if (h!=mid-i+1){
      //      cout << h << " " << "KIR" << " " << mid-i+1 << endl;
        //}
        ll jav=get(1,1,n+1,z,n+1,1);
        if (jav>o){
            o=jav;
            best=i;
        }
    }
    for (int i=L;i<=min(mid,R);i++){
        upd(1,1,n+1,ja[i],0,-1);
        upd(1,1,n+1,ja[i],1,-a[i]);
    }
    if (o==-1) cout << "KIR" << endl;
    dp[id][mid]=o;
    solve(l,mid-1,L,best,id);
    for (int i=L;i<best;i++){
        upd(1,1,n+1,ja[i],0,1);
        upd(1,1,n+1,ja[i],1,a[i]);
    }
    solve(mid+1,r,best,R,id);
    for (int i=L;i<best;i++){
        upd(1,1,n+1,ja[i],0,-1);
        upd(1,1,n+1,ja[i],1,-a[i]);
    }
}
void devide(ll l,ll r,ll L,ll R,ll id){
    if (r<l) return ;
    ll mid=(r+l)/2;
    ll best=L,o=-1;
    for (int i=L;i<=min(mid,R);i++){
        upd(1,1,n+1,ja[i],0,1);
        upd(1,1,n+1,ja[i],1,a[i]);
        if (mid-i-i+2<=0) continue;
        ll z=where(1,1,n+1,mid-i-i+2);
        ll jav=get(1,1,n+1,z,n+1,1);
        if (jav>o){
            o=jav;
            best=i;
        }
    }
    for (int i=L;i<=min(mid,R);i++){
        upd(1,1,n+1,ja[i],0,-1);
        upd(1,1,n+1,ja[i],1,-a[i]);
    }
    dp[id][mid]=o;
    devide(l,mid-1,L,best,id);
    for (int i=L;i<best;i++){
        upd(1,1,n+1,ja[i],0,1);
        upd(1,1,n+1,ja[i],1,a[i]);
    }
    devide(mid+1,r,best,R,id);
    for (int i=L;i<best;i++){
        upd(1,1,n+1,ja[i],0,-1);
        upd(1,1,n+1,ja[i],1,-a[i]);
    }
}
ll findMaxAttraction(int nn,int start,int d,int y[]){
    vector <pii> b;
    start++;
    for (int i=1;i<=nn;i++){
        c[i]=y[i-1];
    }
    for (int i=1;i<=start;i++){
        a[i]=c[i];
    }
    reverse(a+1,a+start+1);
    for (int i=1;i<=start;i++){
        b.pb({a[i],i});
    }
    sort(b.begin(),b.end());
    for (int i=1;i<=b.size();i++){
        ja[b[i-1].S]=i;
    }
    n=start;
    solve(1,d,1,start,0);
  //  cout << " eih3 4w" << endl;
    memset(seg,0,sizeof seg);
    devide(1,d,1,start,1);
    memset(seg,0,sizeof seg);
    b.clear();
    for (int i=start+1;i<=nn;i++){
        a[i-start]=c[i];
    }
    n=nn-start;
    for (int i=1;i<=n;i++){
        b.pb({a[i],i});
    }
    sort(b.begin(),b.end());
    for (int i=0;i<b.size();i++){
        ja[b[i].S]=i+1;
    }
  //  cout << 1 << " " << d << " " << 1 << " " << nn << " " << start  << endl;
   // return 0;
   if (n>0){
    solve(1,d,1,n,2);
    memset(seg,0,sizeof seg);
    devide(1,d,1,n,3);
   }
    ll ans=(dp[0][d]);
   // cout << ans << endl;
    for (int i=0;i<=d-2;i++){
        ans=max(ans,dp[0][i]+dp[3][d-i-2]);
   //     cout << dp[0][i]+dp[3][d-i-2] << endl;
    }
    for (int i=0;i<=d-1;i++){
        ans=max(ans,dp[1][i]+dp[2][d-i-1]);
       // cout << i << " " << dp[1][i] << " " << dp[2][d-i-1] << endl;
    }
    return ans;
}
/*
int cc[12];
int32_t main(){
    for (int i=0;i<12;i++) cin >> cc[i];
    cout << findMaxAttraction(12,4,9,cc) << endl;
}
*/
/*
5
10 2 20 30 1
3 7
*/
//443000133 429885113 57256993 867868565 49902574 245497810 795048239 746594416 782837708 578814954 59738156 922971954

Compilation message (stderr)

holiday.cpp: In function 'void solve(ll, ll, ll, ll, ll)':
holiday.cpp:53:12: warning: unused variable 'h' [-Wunused-variable]
   53 |         ll h=get(1,1,n+1,z,n+1,0);
      |            ^
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:125:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i=1;i<=b.size();i++){
      |                  ~^~~~~~~~~~
holiday.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i=0;i<b.size();i++){
      |                  ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53