Submission #344914

#	Time	Username	Problem	Language	Result	Execution time	Memory
344914		mehrdad_sohrabi	Holiday (IOI14_holiday)	C++14	0 / 100	102 ms	65540 KiB

holiday

#include <bits/stdc++.h>
/// 500 485 462 A4
typedef 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=1e4+100;
ll seg[2][N*4];
ll ja[N];
ll a[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;
        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 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;
    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 c[]){
    vector <pii> b;
    start++;
    for (int i=1;i<=nn;i++){
        a[i]=c[i-1];
    }
    for (int i=1;i<=nn;i++){
        c[i]=a[i];
    }
    memset(a,0,sizeof a);
    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;
    }
    solve(1,d,1,n,2);
    memset(seg,0,sizeof seg);
    devide(1,d,1,n,3);
    ll ans=(dp[0][d]);
    for (int i=0;i<=d-2;i++){
        ans=max(ans,dp[0][i]+dp[3][d-i-2]);
    }
    for (int i=0;i<=d-1;i++){
        ans=max(ans,dp[1][i]+dp[2][d-i-1]);
    }
    return ans;
}
/*
int c[5];
int32_t main(){
    cin >> c[0] >> c[1] >> c[2] >> c[3] >> c[4];
    cout << findMaxAttraction(5,2,7,c) << endl;
}
*/
/*
5
10 2 20 30 1
3 7
*/

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i=1;i<=b.size();i++){
      |                  ~^~~~~~~~~~
holiday.cpp:140:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i=0;i<b.size();i++){
      |                  ~^~~~~~~~~

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