제출 #728508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728508		sentheta	휴가 (IOI14_holiday)	C++17	100 / 100	1688 ms	42320 KiB

holiday

#include"holiday.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const Int N = 1e5+5;

int sz;

#define lc (v+1)
#define rc (v+2*(mid-tl+1))
#define mid (tl+tr)/2
struct Segtree{
	Int sum[8*N]; int cnt[8*N];
	void reset(){
		rep(v,0,2*sz) sum[v] = cnt[v] = 0;
	}
	void upd(int i,Int x,int v=0,int tl=0,int tr=sz-1){
		assert(v<8*N);
		// if(v==0) cout << i _ x << nl;
		if(tl==tr){
			sum[v] = x; cnt[v] = 1; return;
		}
		if(i<=mid) upd(i,x, lc,tl,mid);
		else upd(i,x, rc,mid+1,tr);
		sum[v] = sum[lc] + sum[rc];
		cnt[v] = cnt[lc] + cnt[rc];
	}
	// query sum of largest k values
	Int qry(int k,int v=0,int tl=0,int tr=sz-1){
		assert(v<8*N);
		if(k <= 0) return 0;
		if(cnt[v] <= k) return sum[v];
		Int kr = min(k, cnt[rc]);
		return qry(k-kr, lc,tl,mid) + qry(kr, rc,mid+1,tr);
	}
} segtree;
#undef mid

// what to check at index i
V<int> chk[4*N];
// parent interval
int chkl[4*N], chkr[4*N];
int lastl[4*N], lastr[4*N];

bool bsolved[4*N];

V<Int> solve(const V<Int>& a){
	sz = (int)a.size();
	// dbg(sz);
	V<Int> ret(2*sz,0);
	V<int> last(2*sz,0);

	// sort and find its order
	V<int> iord(sz);
	{
		V<int> ord(sz);
		rep(i,0,sz) ord[i] = i;
		sort(all(ord),[&](int i,int j){
			return a[i] < a[j];
		});
		rep(i,0,sz) iord[ord[i]] = i;
	}
	// for(Int i : iord) cout << i << " ";
	// cout << nl;

	chkl[sz] = 0; chkr[sz] = 2*sz-1;
	lastl[sz] = 0; lastr[sz] = sz-1;
	rep(i,lastl[sz],lastr[sz]+1) chk[i].push_back(sz);

	int repcnt = 0;
	while(1){
		repcnt++;
		// dbg(repcnt);
		assert(repcnt < 30);

		segtree.reset();

		set<int> solved;
		rep(i,0,sz){
			segtree.upd(iord[i],a[i]);

			assert(i < 2*N);
			while(!chk[i].empty()){
				// assert((int)chk[i].size() > 0);
				// dbg(chk[i].back());
				int j = chk[i].back(); chk[i].pop_back();
				bsolved[j] = 1;

				// dbg(j);
				// dbg(solved.size());
				solved.insert(j);
				// if(solved.empty() || solved.back()!=j){
				// 	solved.push_back(j);
				// }

				Int x = segtree.qry(j-i);
				if(x > ret[j]){
					ret[j] = x; last[j] = i;
				}
			}
			// dbg(i);
			assert(chk[i].empty());
			// chk[i] = V<int>();
		}

		// dbg(segtree.qry(3));
		// break;

		bool cont = 0;
		int contcnt = 0;
		for(int j : solved){
			// dbg(j);
			// cout << chkl[j] _ chkr[j] << nl;
			cont |= chkl[j] != chkr[j];

			if(chkl[j] < j){
				int m = (chkl[j] + j-1)/2;
				assert(m < j);
				// dbg(m);
				cont = 1;
				
				chkl[m] = chkl[j]; chkr[m] = j-1;
				lastl[m] = lastl[j]; lastr[m] = last[j];
				
				rep(i,lastl[m],lastr[m]+1){
					contcnt++;
					chk[i].push_back(m);
				}
			}
			if(j < chkr[j]){
				int m = (j+1 + chkr[j])/2;
				assert(j < m);
				// dbg(m);
				cont = 1;
				
				chkl[m] = j+1; chkr[m] = chkr[j];
				lastl[m] = last[j]; lastr[m] = lastr[j];
				
				rep(i,lastl[m],lastr[m]+1){
					contcnt++;
					chk[i].push_back(m);
				}
			}
		}

		// dbg(contcnt);
		// dbg(solved.size());
		// if(contcnt==400004) for(int j : solved){
		// 	dbg(j);
		// 	// if(chkl[j] < j){
		// 	// 	int m = (chkl[j] + j-1)/2;
		// 	// 	dbg(m);
		// 	// 	dbg(chkl[m]); dbg(chkr[m]);
		// 	// 	dbg(lastl[m]); dbg(lastr[m]);
		// 	// }
		// 	// if(j < chkr[j]){
		// 	// 	int m = (j+1 + chkr[j])/2;
		// 	// 	dbg(m);
		// 	// 	dbg(chkl[m]); dbg(chkr[m]);
		// 	// 	dbg(lastl[m]); dbg(lastr[m]);
		// 	// }
		// }
		if(!cont) break;
	}

	// Int prv = 0;
	// for(Int x : ret){
	// 	assert(prv <= x); prv = x;
	// }
	return ret;
}


Int findMaxAttraction(int n,int s,int d,int a[]){
	Int ans = 0;

	// V<Int> v = {20,0,2,0,10};
	// for(Int x : v) cout << x << " ";
	// cout << nl;
	// for(Int x : solve(v)) cout << x << " ";
	// cout << nl;
	// return ans;

	rep(loop,0,2){
		V<Int> vl = {0};
		for(int i=s-1; i>=0; i--){
			vl.push_back(a[i]);
		}
		V<Int> vr = {a[s]};
		for(int i=s+1; i<n; i++){
			vr.push_back(0);
			vr.push_back(a[i]);
		}

		vl = solve(vl);
		// if(vl.empty()) vl = {0};

		// dbg(l.size());
		// for(Int x : l) cout << x << " ";
		// cout << nl;
		// dbg(vl.size());
		// for(Int x : vl) cout << x << " ";
		// cout << nl << nl;

		vr = solve(vr);
		// if(vr.empty()) vr = {0};

		// dbg(r.size());
		// for(Int x : r) cout << x << " ";
		// cout << nl;
		// dbg(vr.size());
		// for(Int x : vr) cout << x << " ";
		// cout << nl << nl;

		// go right, then left
		for(Int dl=0,dr=d; dr>=0; dl++,dr--){
			Int ansl = dl<(Int)vl.size() ? vl[dl] : vl.back();
			Int ansr = dr<(Int)vr.size() ? vr[dr] : vr.back();

			ans = max(ans, ansl+ansr);
		}
		// dbg(ans);

		// reverse all
		reverse(a,a+n);
		s = n-1-s;
		// cout << nl << nl;
	}

	return ans;

}

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