Submission #538532

#	Time	Username	Problem	Language	Result	Execution time	Memory
538532		czhang2718	Holiday (IOI14_holiday)	C++17	100 / 100	1408 ms	6344 KiB

holiday

#include"holiday.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define pb push_back
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define f first
#define s second

const int N=100000;
ll ans;
int A[N];
int n, d;

int cnt[4*N];
int pos[N];
ll sum[4*N];


// ------------Segtree------------------
void upd(int i, int v, int x, int lx, int rx){
    if(rx-lx==1){
        cnt[x]=(v>0);
        sum[x]=v;
        return;
    }
    int m=(lx+rx)/2;
    if(i<m) upd(i, v, 2*x+1, lx, m);
    else upd(i, v, 2*x+2, m, rx);
    sum[x]=sum[2*x+1]+sum[2*x+2];
    cnt[x]=cnt[2*x+1]+cnt[2*x+2];
}

void upd(int i, int v){ upd(i, v, 0, 0, n); }

ll walk(int k, int x, int lx, int rx){
    if(k>=cnt[x]) return sum[x];
    if(k<=0) return 0;
    int m=(lx+rx)/2;
    if(cnt[2*x+2]<=k) return sum[2*x+2]+walk(k-cnt[2*x+2], 2*x+1, lx, m);
    else return walk(k, 2*x+2, m, rx);
}

ll walk(int k) { return walk(k, 0, 0, n); }

// ----------------END -------------------



void solve(int l, int r, int a, int b, int start){
    if(r<=l || b<a) return;
    // cout << "solve " << l << " " << r << " " << a << " " << b << " " << start << "\n";

    int m=(l+r)/2;
    rep(i,l,m) upd(pos[i], A[i]);
    pair<ll, int> opt;
    for(int i=b; i>=a; i--){
        if(i!=l) upd(pos[i], A[i]);
        int dist=m-i+m-start;
        ll w=walk(d-dist);
        opt=max(opt, {w, i});
    }
    // cout << m << " " << a << " "<< b << " opt " << opt.f << " " << opt.s << "\n";
    // opt.s*=-1; // ??
    ans=max(ans, opt.f);
    rep(i,l,m) upd(pos[i], 0);
    for(int i=b; i>=a; i--) if(i!=l) upd(pos[i], 0);
    rep(i,opt.s+1,b) upd(pos[i], A[i]);
    solve(l, m, a, opt.s, start);

    rep(i,l,m) upd(pos[i], A[i]);
    rep(i,opt.s+1,b) upd(pos[i], 0);
    solve(m+1, r, opt.s, b, start);

    rep(i,l,m) upd(pos[i], 0);
}

void go(int start){
    solve(start, n, 0, start, start);
}

void line(int start){
    rep(i,start,n-1){
        upd(pos[i], A[i]);
        // cout << i << " " << walk(d-(i-start)) << "\n";
        ans=max(ans, walk(d-(i-start)));
    }
    rep(i,start,n-1){
        upd(pos[i], 0);
    }
    for(int i=start; i>=0; i--){
        upd(pos[i], A[i]);
        ans=max(ans, walk(d-(start-i)));
    }
    for(int i=start; i>=0; i--){
        upd(pos[i], 0);
    }
}

long long int findMaxAttraction(int nn, int start, int D, int attraction[]) {
    d=D;
    n=nn;
    rep(i,0,n-1) A[i]=attraction[i];

    vector<pair<int, int>> v;
    rep(i,0,n-1) v.pb({A[i], i});
    sort(v.begin(), v.end());
    rep(i,0,n-1) pos[v[i].s]=i;
    
    line(start);
    go(start);
    for(int i=0; n-1-i>i; i++) swap(A[i], A[n-1-i]), swap(pos[i], pos[n-1-i]);
    go(n-1-start); 
    return ans;
}

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