oj.uz

Submission #519831

# Submission time Handle Problem Language Result Execution time Memory
519831 2022-01-27T11:31:15 Z AdamGS Holiday (IOI14_holiday) C++17
100 / 100
 1167 ms 37300 KB 
#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=4e5+7;
int ile[4*LIM], N;
pair<ll,ll>T[4*LIM], P[4*LIM];
ll sum[4*LIM], ans[4*LIM];
void upd1(int v, int x) {
	v+=N;
	while(v) {
		ile[v]+=x;
		v/=2;
	}
}
int znajdz(int k) {
	int v=1;
	while(v<N) {
		v*=2;
		if(ile[v]<k) {
			k-=ile[v];
			++v;
		}
	}
	return v-N;
}
void upd2(int v, ll x) {
	v+=N;
	while(v) {
		sum[v]+=x;
		v/=2;
	}
}
ll cnt(int l, int r) {
	l+=N; r+=N;
	ll x=sum[l];
	if(l!=r) x+=sum[r];
	while(l/2!=r/2) {
		if(l%2==0) x+=sum[l+1];
		if(r%2==1) x+=sum[r-1];
		l/=2; r/=2;
	}
	return x;
}
void dc(int l, int r, int a, int b, int n) {
	if(b<a) return;
	int mid=(a+b)/2;
	ll ma=0, gdzie=l;
	for(int i=l; i<=r; ++i) {
		if(i<n) {
			upd1(T[i].nd, 1);
			upd2(T[i].nd, T[i].st);
		}
		if(mid==i && ma==0) {
			ma=0;
			gdzie=i;
		}
		if(0<mid-i && mid-i<=i+1) {
			ll p=cnt(0, znajdz(mid-i));
			if(p>ma) {
				ma=p;
				gdzie=i;
			}
		}
	}
	for(int i=r; i>=gdzie; --i) {
		if(i<n) {
			upd1(T[i].nd, -1);
			upd2(T[i].nd, -T[i].st);
		}
	}
	dc(gdzie, r, mid+1, b, n);
	for(int i=gdzie-1; i>=l; --i) {
		if(i<n) {
			upd1(T[i].nd, -1);
			upd2(T[i].nd, -T[i].st);
		}
	}
	dc(l, gdzie, a, mid-1, n);
	ans[mid]=ma;
}
vector<ll>licz(vector<ll>V) {
	int n=V.size();
	N=1;
	while(N<2*n) N*=2;
	rep(i, 2*N) ile[i]=ans[i]=sum[i]=0;
	rep(i, n) P[i]={V[i], i};
	sort(P, P+n);
	reverse(P, P+n);
	rep(i, n) T[P[i].nd]={P[i].st, i};
	dc(0, n-1, 0, 2*n-1, n);
	vector<ll>W;
	rep(i, 2*n) W.pb(ans[i]);
	return W;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	vector<ll>V, A1, A2, B1, B2;
	for(int i=start; i<n; ++i) V.pb(attraction[i]);
	A1=licz(V);
	V.clear();
	for(int i=start; i<n; ++i) {
		V.pb(attraction[i]);
		V.pb(0);
	}
	A2=licz(V);
	V.clear();
	V.pb(0);
	for(int i=start-1; i>=0; --i) V.pb(attraction[i]);
	B1=licz(V);
	V.clear();
	V.pb(0);
	for(int i=start-1; i>=0; --i) {
		V.pb(0);
		V.pb(attraction[i]);
	}
	B2=licz(V);
	ll ma=0;
	rep(i, min(int(A1.size()), d+1)) {
		ma=max(ma, A1[i]+B2[min(d-i, int(B2.size()-1))]);
	}
	rep(i, min(int(A2.size()), d+1)) {
		ma=max(ma, A2[i]+B1[min(d-i, int(B1.size()-1))]);
	}
	return ma;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1127 ms 36424 KB Output is correct
2 Correct 893 ms 36616 KB Output is correct
3 Correct 1043 ms 36724 KB Output is correct
4 Correct 924 ms 36732 KB Output is correct
5 Correct 1086 ms 35776 KB Output is correct
6 Correct 275 ms 10212 KB Output is correct
7 Correct 588 ms 18912 KB Output is correct
8 Correct 688 ms 20204 KB Output is correct
9 Correct 186 ms 9252 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1904 KB Output is correct
2 Correct 20 ms 1868 KB Output is correct
3 Correct 20 ms 1904 KB Output is correct
4 Correct 17 ms 1740 KB Output is correct
5 Correct 15 ms 1416 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 5 ms 972 KB Output is correct
8 Correct 5 ms 1000 KB Output is correct
9 Correct 5 ms 972 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 36424 KB Output is correct
2 Correct 1155 ms 37300 KB Output is correct
3 Correct 438 ms 11460 KB Output is correct
4 Correct 16 ms 1328 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 6 ms 940 KB Output is correct
8 Correct 1144 ms 23368 KB Output is correct
9 Correct 1167 ms 23456 KB Output is correct