Submission #573462

#	Time	Username	Problem	Language	Result	Execution time	Memory
573462		perchuts	Holiday (IOI14_holiday)	C++17	100 / 100	436 ms	7184 KiB

holiday

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "holiday.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
//dp[i][j]: visito as cidades [i,j] (i<=start<=j). vamos gastar j-i + j-start dias andando
//logo, queremos a soma dos max(0,min(d - (2j - start - i),j-i+1)) maiores numeros entre [i,j]. 
//igualzinho o cake3, mas nao da pra usar persistencia nesse por causa da memoria...
//preciso achar os m maiores numeros entre [i,j] em log

pair<ll,int> seg[4*maxn];
ll v[maxn];
vector<int>ord;
int n, _ord[maxn];

void build(int i,int l,int r){
    if(l==r){
        seg[i] = {v[ord[l]],1};
        return;
    } 
    int md = (l+r)/2;
    build(2*i,l,md), build(2*i+1,md+1,r);
    seg[i].first = seg[2*i].first + seg[2*i+1].first;
    seg[i].second = seg[2*i].second + seg[2*i+1].second;
}

int curL, curR, st;
ll ans = 0;

void update(int i,int l,int r,int x,bool type){
    if(l>x||r<x)return;
    if(l==r){
        seg[i] = (type?make_pair(v[ord[l]],1):make_pair(0ll,0));
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,type), update(2*i+1,md+1,r,x,type);
    seg[i].first = seg[2*i].first + seg[2*i+1].first;
    seg[i].second = seg[2*i].second + seg[2*i+1].second;
}

ll query(int i,int l,int r,int qnt){
    if(l==r)return qnt?seg[i].first:0;
    int md = (l+r)/2;
    if(seg[2*i+1].second>=qnt)return query(2*i+1,md+1,r,qnt);
    return seg[2*i+1].first + query(2*i,l,md,qnt-seg[2*i+1].second);
}

ll query(int l,int r,int d){
    while(curL<l)update(1,1,n,_ord[curL],0),curL++;
    while(curL>l)curL--,update(1,1,n,_ord[curL],1);
    while(curR<r)curR++,update(1,1,n,_ord[curR],1);
    while(curR>r)update(1,1,n,_ord[curR],0),curR--;
    return query(1,1,n,d);
}

void compute(int l,int r,int lx,int rx,int d){
    if(l>r)return;
    int md = (l+r)/2;
    ll best = -1, opt = -1;
    for(int i=lx;i<=min(md,rx);++i){
        ll cur = query(i,md, max(0,max(d - (2*md - st - i),d - (md + st - 2*i))));
        if(ckmax(best,cur))opt = i;
    }
    assert(opt!=-1);
    ckmax(ans,best);
    compute(l,md-1,lx,opt,d), compute(md+1,r,opt,rx,d);
}

ll findMaxAttraction(int N, int start, int d, int attraction[]) {
    ++start, n = N;

    for(int i=0;i<n;++i)v[i+1] = ll(attraction[i]);
    v[0] = -1; 
    ord.resize(n+1),iota(all(ord),0),sort(all(ord), [&](int x,int y){
        return v[x] < v[y];
    });    

    for(int i=1;i<=n;++i)_ord[ord[i]] = i;

    build(1,1,n);
    curL = 1, curR = n, st = start;

    compute(st,n,1,st,d);

    return ans;
}

// int attraction[maxn];

// int main(){
//     int n, start, d;cin>>n>>start>>d;
//     for(int i=0;i<n;++i)cin>>attraction[i];
//     cout<<findMaxAttraction(n,start,d,attraction)<<endl;
// }

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