Submission #1031099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031099		MarwenElarbi	Holiday (IOI14_holiday)	C++17	100 / 100	750 ms	16004 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=3e5+5;
pair<ll,ll> segtree[nax*4];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]={0,0};
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos].fi=segtree[pos*2+1].fi+segtree[pos*2+2].fi;
    segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
    return;
}
void update(int pos,int l,int r,int idx,ll value){
    if(l==r){
        segtree[pos].fi=value;
        segtree[pos].se=( value > 0 ? 1 : 0);
        return;
    }
    int mid=(r+l)/2;
    if(mid>=idx) update(pos*2+1,l,mid,idx,value);
    else update(pos*2+2,mid+1,r,idx,value);
    segtree[pos].fi=segtree[pos*2+1].fi+segtree[pos*2+2].fi;
    segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
    //cout <<l<<" "<<r<<" "<<segtree[pos].fi<<endl;
    return;
}
long long query(int pos,int l,int r,int cnt){
    if(l==r) return (cnt>=segtree[pos].se ? segtree[pos].fi : 0);
    int mid=(r+l)/2;
    if(cnt<=0) return 0;
    if(cnt>=segtree[pos*2+2].se){
        return query(pos*2+1,l,mid,cnt-segtree[pos*2+2].se)+segtree[pos*2+2].fi;
    }else{
        return query(pos*2+2,mid+1,r,cnt);
    }
}
vector<int> a;
vector<int> b;
pair<ll,int> lefty[nax];
pair<ll,int> righty[nax];
vector<int> cnt(nax);
int m;
void daq(int l,int r,int optl,int optr,int idx){
    int mid=(r+l)/2;
    for (int i = optl; i <= optr; ++i)
    {
        update(0,0,m-1,cnt[i],(idx ? b[i] : a[i]));
        ll cur=query(0,0,m-1,mid-i);
        if((idx ? righty[mid].fi : lefty[mid].fi) < cur){
            (idx ? righty[mid] : lefty[mid])={cur,i};
        }
    }
    for (int i = optr; i >= optl; --i)
    {
        update(0,0,m-1,cnt[i],0);
    }
    if(l==r) return;
    daq(l,mid,optl,(idx ? righty[mid].se : lefty[mid].se),idx);
    for (int i = optl; i <= (idx ? righty[mid].se : lefty[mid].se); ++i)
    {
        update(0,0,m-1,cnt[i],(idx ? b[i] : a[i]));
    }
    daq(mid+1,r,(idx ? righty[mid].se : lefty[mid].se),optr,idx);
    for (int i = (idx ? righty[mid].se : lefty[mid].se); i <= optr; ++i)
    {
        update(0,0,m-1,cnt[i],(idx ? b[i] : a[i]));
    }
    return;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<pair<int,int>> tab;
    for (int i = 0; i < start; ++i)
    {
        a.pb(attraction[i]);
    }
    for (int i = start; i < n; ++i)
    {
        b.pb(attraction[i]);
    }
    reverse(a.begin(),a.end());
    for (int i = 0; i < a.size(); ++i)
    {
        tab.pb({a[i],i});
    }
    sort(tab.begin(),tab.end());
    for (int i = 0; i < tab.size(); ++i)
    {
        cnt[tab[i].se]=i;
    }
    m=a.size();
    if(a.size()){
        build(0,0,m-1);
        daq(0,d,0,m-1,0);
    }
    tab.clear();
    for (int i = 0; i < b.size(); ++i)
    {
        tab.pb({b[i],i});
    }
    sort(tab.begin(),tab.end());
    for (int i = 0; i < tab.size(); ++i)
    {
        cnt[tab[i].se]=i;
    }
    m=b.size();
    if(b.size()){
        build(0,0,m-1);
        daq(0,d,0,m-1,1);
    }
    long long ans=0;
    for (int i = 0; i <= d; ++i)
    {
        ans=max(ans,righty[i].fi+( d >= righty[i].se+i+1 ? lefty[d-righty[i].se-i-1].fi : 0));
        if(i<d) ans=max(ans,lefty[i].fi+( d >= lefty[i].se+i+2 ? righty[d-lefty[i].se-i-2].fi : 0));
    }
    return ans;
}

Compilation message (stderr)

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

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