제출 #1163739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163739		peteza	Holiday (IOI14_holiday)	C++20	100 / 100	2677 ms	11088 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<ll, ll> segm[400005];
int pospos[100005], atar[100005];
int D, ST, N;
int sl=0, sr=-1;

void upd(int idx, int l, int r, int tgt, pair<int, int> val) {
	if(l==r) {
		segm[idx].first += val.first;
		segm[idx].second += val.second;
		return;
	}
	int mid = (l+r)>>1;
	if(tgt <= mid) upd(idx*2+1, l, mid, tgt, val);
	else upd(idx*2+2, mid+1, r, tgt, val);
	segm[idx].first = segm[idx*2+1].first + segm[idx*2+2].first;
	segm[idx].second = segm[idx*2+1].second + segm[idx*2+2].second;
}

ll qr(int idx, int l, int r, int k) {
	if(segm[idx].first <= k) return segm[idx].second;
	int mid = (l+r)>>1;
	if(segm[idx*2+2].first >= k) return qr(idx*2+2, mid+1, r, k);
	return qr(idx*2+1, l, mid, k-segm[idx*2+2].first) + segm[idx*2+2].second;
}

ll getmxbet(int cnt) {
	if(cnt <= 0) return 0;
	return qr(0, 0, N-1, cnt);
}

ll cbans=0;

void setdpup(int l, int r) {
	while(l<sl) {sl--; upd(0, 0, N-1, pospos[sl], {1, atar[sl]});}
	while(sr<r) {sr++; upd(0, 0, N-1, pospos[sr], {1, atar[sr]});}
	while(sl<l) {upd(0, 0, N-1, pospos[sl], {-1, -atar[sl]}); sl++;}
	while(r<sr) {upd(0, 0, N-1, pospos[sr], {-1, -atar[sr]}); sr--;}
}

queue<pair<pair<int, int>, pair<int, int>>> Q;

void rundp1(int l, int r, int posl, int posr) {
	if(l>r) return;
	int mid = (l+r)/2;
	setdpup(mid, max(posl, mid));
	pair<ll, ll> bestans(getmxbet(D-ST-max(posl,mid)+2*mid), max(posl, mid));
	for(int i=max(posl, mid)+1; i<=posr; i++) {
		setdpup(mid, i);
		bestans = max(bestans, {getmxbet(D-ST-i+2*mid), i});
		
	}
	cbans = max(cbans, bestans.first);
	Q.push({{l, mid-1}, {posl, bestans.second}});
	Q.push({{mid+1, r}, {bestans.second, posr}});
}

void rundp2(int l, int r, int posl, int posr) {
	if(l>r) return;
	int mid = (l+r)/2;
	setdpup(posl, mid);
	pair<ll, ll> bestans(getmxbet(D-2*mid+ST+posl), posl);
	for(int i=posl+1; i<=min(mid, posr); i++) {
		setdpup(i, mid);
		bestans = max(bestans, {getmxbet(D-2*mid+ST+i), i});
	}
	cbans = max(cbans, bestans.first);
	Q.push({{l, mid-1}, {posl, bestans.second}});
	Q.push({{mid+1, r}, {bestans.second, posr}});
}

bool run2=0;

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	cbans=0; N=n; sl=0; sr =-1;
	D=d; ST=start;
	vector<pair<int, int>> idxval;
	for(int i=0;i<4*n;i++) segm[i] = {0,0};
	for(int i=0;i<n;i++) {
		atar[i] = attraction[i];
		idxval.emplace_back(attraction[i], i);
	}
	sort(idxval.begin(), idxval.end());
	for(int i=0;i<n;i++) {pospos[idxval[i].second]=i;}
	rundp1(0, start, 0, n-1);
	while(!Q.empty()) {
		auto e = Q.front(); Q.pop();
		rundp1(e.first.first, e.first.second, e.second.first, e.second.second);
	}
	rundp2(start, n-1, 0, n-1);
	while(!Q.empty()) {
		auto e = Q.front(); Q.pop();
		rundp2(e.first.first, e.first.second, e.second.first, e.second.second);
	}
	if(run2) return cbans;
	run2=1;
	for(int i=0;i<n/2;i++) swap(atar[i], atar[n-1-i]);
	return max(cbans, findMaxAttraction(n, n-1-start, d, atar));
}

/*
int val[5] = {7, 5, 1, 10, 12};

int main() {
	cout << findMaxAttraction(5, 2, 8, val);
	//cout << qr(roots[2], roots[3], 5);
}*/

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