oj.uz

Submission #344983

# Submission time Handle Problem Language Result Execution time Memory
344983 2021-01-06T20:40:11 Z mehrdad_sohrabi Holiday (IOI14_holiday) C++14
100 / 100
 3400 ms 31556 KB 
#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;
        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=0;
    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]);
    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 cc[20];
int32_t main(){
    for (int i=0;i<20;i++) cin >> cc[i];
    cout << findMaxAttraction(20,19,50,cc) << endl;
}
*/
/*
5
10 2 20 30 1
3 7
*/

Compilation message

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:119: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]
  119 |     for (int i=1;i<=b.size();i++){
      |                  ~^~~~~~~~~~
holiday.cpp:137: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]
  137 |     for (int i=0;i<b.size();i++){
      |                  ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19180 KB Output is correct
2 Correct 14 ms 19180 KB Output is correct
3 Correct 12 ms 19180 KB Output is correct
4 Correct 14 ms 19180 KB Output is correct
5 Correct 14 ms 19180 KB Output is correct
6 Correct 16 ms 19180 KB Output is correct
7 Correct 14 ms 19180 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2983 ms 29788 KB Output is correct
2 Correct 2130 ms 30016 KB Output is correct
3 Correct 2956 ms 30128 KB Output is correct
4 Correct 2143 ms 29992 KB Output is correct
5 Correct 3088 ms 27268 KB Output is correct
6 Correct 1069 ms 26356 KB Output is correct
7 Correct 1628 ms 24384 KB Output is correct
8 Correct 1897 ms 24676 KB Output is correct
9 Correct 836 ms 27748 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19436 KB Output is correct
2 Correct 55 ms 19436 KB Output is correct
3 Correct 56 ms 19564 KB Output is correct
4 Correct 56 ms 19436 KB Output is correct
5 Correct 52 ms 19436 KB Output is correct
6 Correct 23 ms 19308 KB Output is correct
7 Correct 20 ms 19180 KB Output is correct
8 Correct 21 ms 19180 KB Output is correct
9 Correct 21 ms 19180 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3119 ms 27564 KB Output is correct
2 Correct 3400 ms 31556 KB Output is correct
3 Correct 428 ms 21220 KB Output is correct
4 Correct 38 ms 19308 KB Output is correct
5 Correct 20 ms 19180 KB Output is correct
6 Correct 21 ms 19180 KB Output is correct
7 Correct 22 ms 19180 KB Output is correct
8 Correct 2821 ms 23800 KB Output is correct
9 Correct 2833 ms 23572 KB Output is correct