oj.uz

Submission #483703

# Submission time Handle Problem Language Result Execution time Memory
483703 2021-10-31T20:22:28 Z FEDIKUS Holiday (IOI14_holiday) C++17
100 / 100
 777 ms 17144 KB 
#include"holiday.h"
#include<bits/stdc++.h>
#define xx first
#define yy second

using namespace std;

typedef long long ll;

const ll maxd=2.5e5+10;

ll siz=0;

void add(ll t,ll v,vector<pair<ll,ll> > &segt,ll ind=1,ll l=0,ll r=siz){
    if(l==r){
        segt[ind].xx+=v;
        if(segt[ind].xx==0) segt[ind].yy=0;
        else segt[ind].yy=1;
        return;
    }
    ll mid=l+(r-l)/2;
    if(t<=mid) add(t,v,segt,2*ind,l,mid);
    else add(t,v,segt,2*ind+1,mid+1,r);
    segt[ind].xx=segt[2*ind].xx+segt[2*ind+1].xx;
    segt[ind].yy=segt[2*ind].yy+segt[2*ind+1].yy;
}

ll query(ll t,vector<pair<ll,ll> > &segt,ll ind=1,ll l=0,ll r=siz){
    ll mid=l+(r-l)/2;
    ll ret=0;
    if(segt[ind].yy<=t) return segt[ind].xx;
    ret+=query(min(segt[2*ind].yy,ll(t)),segt,2*ind,l,mid);
    if(segt[2*ind].yy<t) ret+=query(t-segt[2*ind].yy,segt,2*ind+1,mid+1,r);
    return ret;
}

void dc(ll l,ll r,ll bl,ll br,vector<pair<ll,ll> > &atr,vector<ll> &where,vector<ll> &res,vector<ll> &pos,vector<pair<ll,ll> > &segt){
    if(l>r) return;
    ll mid=l+(r-l)/2;
    ll b=0,bpos=bl;
    for(ll i=bl;i<=br;i++){
        add(where[i],atr[where[i]].xx,segt);
        if(i>=mid) continue;
        ll q=0;
        if((q=query(mid-i,segt))>b){
            b=q;
            bpos=i;
        }
    }
    res[mid]=b;
    pos[mid]=bpos;
    for(ll i=bpos;i<=br;i++) add(where[i],-atr[where[i]].xx,segt);
    dc(mid+1,r,bpos,br,atr,where,res,pos,segt);
    for(ll i=bl;i<bpos;i++) add(where[i],-atr[where[i]].xx,segt);
    dc(l,mid-1,bl,bpos,atr,where,res,pos,segt);
}

void solve(vector<pair<ll,ll> > &atr,vector<ll> &res,vector<ll> &pos,ll d){
    if(atr.empty()) return;
    vector<ll> where(atr.size());
    for(ll i=0;i<atr.size();i++) where[atr[i].yy]=i;
    vector<pair<ll,ll> > segt(4*atr.size()+10);
    siz=atr.size()-1;
    dc(0,d,0,atr.size()-1,atr,where,res,pos,segt);
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<pair<ll,ll> > left,right;
    vector<ll> rleft(d+1),rright(d+1);
    vector<ll> pleft(d+1),pright(d+1);
    for(ll i=0;i<n;i++){
        if(i<start) left.push_back(make_pair(attraction[i],start-i-1));
        else right.push_back(make_pair(attraction[i],i-start));
    }
    sort(left.begin(),left.end(),greater<pair<ll,ll> >()); sort(right.begin(),right.end(),greater<pair<ll,ll> >());
    solve(right,rright,pright,d);
    solve(left,rleft,pleft,d);
    ll res=0;
    for(ll i=0;i<=d;i++){
        ll ost=d-pright[i]-i-1;
        if(ost>0) res=max(res,rright[i]+rleft[ost]);
        else res=max(res,rright[i]);
    }
    for(ll i=0;i<d;i++){
        ll ost=d-pleft[i]-i-2;
        if(ost>0) res=max(res,rleft[i]+rright[ost]);
        else res=max(res,rleft[i]);
    }
    return res;
}
/*
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13
*/

Compilation message

holiday.cpp: In function 'void solve(std::vector<std::pair<long long int, long long int> >&, std::vector<long long int>&, std::vector<long long int>&, ll)':
holiday.cpp:61:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(ll i=0;i<atr.size();i++) where[atr[i].yy]=i;
      |                ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 588 KB Output is correct
2 Correct 0 ms 588 KB Output is correct
3 Correct 0 ms 588 KB Output is correct
4 Correct 0 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 684 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 15636 KB Output is correct
2 Correct 577 ms 15556 KB Output is correct
3 Correct 646 ms 15556 KB Output is correct
4 Correct 570 ms 15540 KB Output is correct
5 Correct 777 ms 12684 KB Output is correct
6 Correct 257 ms 8772 KB Output is correct
7 Correct 392 ms 7804 KB Output is correct
8 Correct 488 ms 8764 KB Output is correct
9 Correct 195 ms 9796 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1228 KB Output is correct
2 Correct 12 ms 1100 KB Output is correct
3 Correct 12 ms 1100 KB Output is correct
4 Correct 12 ms 972 KB Output is correct
5 Correct 11 ms 996 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 17132 KB Output is correct
2 Correct 741 ms 17144 KB Output is correct
3 Correct 241 ms 3880 KB Output is correct
4 Correct 11 ms 844 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 726 ms 8120 KB Output is correct
9 Correct 730 ms 8252 KB Output is correct