제출 #1163850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163850		peteza	휴가 (IOI14_holiday)	C++20	100 / 100	1460 ms	9700 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;

bool run2 = 0;

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);
		if(getmxbet(D-ST-i+2*mid) > bestans.first) {bestans = {getmxbet(D-ST-i+2*mid), i};}
		//bestans = max(bestans, {getmxbet(D-ST-i+2*mid), i});
	}
	//if(!run2 && mid == 31225) {cout << run2 << ' ' << ST << " -> " << mid << " -> " << bestans.second << " ( " << posl << ", " << posr << ") " << '\n';};
	//if(bestans.first == 265279695060ll) {cout << run2 << ' ' << ST << " -> " << mid << " -> " << bestans.second << " ( " << posl << ", " << posr << ") " << '\n';}
	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;
//if(mid == 3) cout << posl << ' ' << posr<<'\n';
	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});
	}
//if(mid==3) cout << bestans.first << "->"<< bestans.second <<'\n';
	cbans = max(cbans, bestans.first);
	Q.push({{l, mid-1}, {posl, bestans.second}});
	Q.push({{mid+1, r}, {bestans.second, posr}});
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	if(!run2) 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);
	}
	return cbans;
	/*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));*/
}

/*
ifstream f("testfileahh.txt");


int n, start, d;
int val[100005] = {10, 2, 20, 30, 1};

int main() {
	ifstream f("testfileahh.txt");
	cin.rdbuf(f.rdbuf());
	cin >> n >> start >> d;
	for(int i=0;i<n;i++) cin >> val[i];
	cout << findMaxAttraction(n, start, d, val);
	//cout << qr(roots[2], roots[3], 5);
}*/

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