Submission #979995

#	Time	Username	Problem	Language	Result	Execution time	Memory
979995		thomas_li	Holiday (IOI14_holiday)	C++17	77 / 100	1214 ms	12808 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A,class B> void cmx(A& x, B y) {x=max<A>(x,y);}
template<class A,class B> void cmn(A& x, B y) {x=min<A>(x,y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
struct FT {
	vector<ll> s;
	FT(int n) : s(n) {}
	void update(int pos, ll dif) { // a[pos] += dif
		for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
	}
	ll query(int pos) { // sum of values in [0, pos)
		ll res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
	int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
		// Returns n if no sum is >= sum, or -1 if empty sum is.
		if (sum <= 0) return -1;
		int pos = 0;
		for (int pw = 1 << 25; pw; pw >>= 1) {
			if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
				pos += pw, sum -= s[pos-1];
		}
		return pos;
	}
};
typedef vector<ll> vll;
vll calc(vi& a, int mul, int len, int base = 0){
    int n = sz(a);
    vll res(len);
    if(!n) return res;
    vi vals = a; sort(all(vals),greater<>()); vals.erase(unique(all(vals)),vals.end());
    FT cnt(sz(vals)),sum(sz(vals));
    auto add = [&](int x, int v){
        int pos = lower_bound(all(vals),x,greater<>())-vals.begin();
        cnt.update(pos,v);  
        sum.update(pos,v*x);
    };
    auto qry = [&](int num){
        if(num <= 0) return 0ll;
        int pos = cnt.lower_bound(num+1);
        ll ext = num-cnt.query(pos);
        /*
        if(ext < 0){
            cerr << "WUT " << num << " " << ext << "\n";
            exit(0);
        }*/
        assert(ext >= 0); 
        //int cnext = (pos == sz(cnt.s) ? 0 : cnt.query(pos+1)-cnt.query(pos));
        ll cur = sum.query(pos); 
        if(pos < sz(vals)) cur += ext * vals[pos]; 
        return cur;
    };
    auto rec = [&](auto&& rec, int l, int r, int optl, int optr){
        if(l > r) return; 
        int mid = (l+r)/2; pair<ll,int> ans{-1,0};
        for(int i = optl; i <= optr; i++){
            int rem = mid-(i+base)*mul;
            add(a[i],1); 
            cmx(ans,pair<ll,int>{qry(rem),-i});         
        } 
        assert(ans.FS >= 0);
        res[mid] = ans.FS; ans.SD *= -1;
        for(int i = optr; i >= ans.SD; i--){
            add(a[i],-1);
        } 
        rec(rec,mid+1,r,ans.SD,optr);
        for(int i = ans.SD-1; i >= optl; i--){
            add(a[i],-1);
        } 
        rec(rec,l,mid-1,optl,ans.SD);
    };
    rec(rec,0,sz(res)-1,0,n-1);
    return res;
}
long long int findMaxAttraction(int n, int s, int d, int attraction[]){
    vi a{attraction,attraction+n};
    vi rit{a.begin()+s,a.end()};
    vi lft{a.begin(),a.begin()+s};
    reverse(all(lft));
    auto rf = calc(rit,2,3*n);
    auto rs = calc(rit,1,3*n);
    auto lf = calc(lft,2,3*n,1);
    auto ls = calc(lft,1,3*n,1);
    ll ans = 0;
    rep(i,0,d+1){
        cmx(ans,rf[i]+ls[d-i]);
        cmx(ans,rs[i]+lf[d-i]);
    }
    return ans;
}

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