oj.uz

Submission #483707

# Submission time Handle Problem Language Result Execution time Memory
483707 2021-10-31T21:38:14 Z FEDIKUS Holiday (IOI14_holiday) C++17
100 / 100
 664 ms 17204 KB 
#pragma GCC optimize("Ofast")
#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:62: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]
   62 |     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 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 0 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct
7 Correct 0 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 15664 KB Output is correct
2 Correct 487 ms 15548 KB Output is correct
3 Correct 601 ms 15556 KB Output is correct
4 Correct 517 ms 15564 KB Output is correct
5 Correct 664 ms 12656 KB Output is correct
6 Correct 216 ms 8816 KB Output is correct
7 Correct 344 ms 7856 KB Output is correct
8 Correct 431 ms 8652 KB Output is correct
9 Correct 170 ms 9780 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1100 KB Output is correct
2 Correct 11 ms 1228 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 10 ms 972 KB Output is correct
5 Correct 10 ms 992 KB Output is correct
6 Correct 3 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 594 ms 17132 KB Output is correct
2 Correct 659 ms 17204 KB Output is correct
3 Correct 242 ms 3856 KB Output is correct
4 Correct 9 ms 844 KB Output is correct
5 Correct 3 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 646 ms 7360 KB Output is correct
9 Correct 655 ms 7484 KB Output is correct