oj.uz

Submission #338819

# Submission time Handle Problem Language Result Execution time Memory
338819 2020-12-24T03:40:15 Z alishahali1382 Holiday (IOI14_holiday) C++14
100 / 100
 933 ms 10584 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll ans; // :))
int n, start, D, k, u, v, x, y, t, a, b;
int A[MAXN], L, R;

struct Set{
	ll sum, sz;
	int mark[MAXN];
	priority_queue<pii, vector<pii>, greater<pii>> X;
	priority_queue<pii> Y;
	inline void relax(){
		while (X.size() && mark[X.top().second]!=1) X.pop();
		while (Y.size() && mark[Y.top().second]!=2) Y.pop();
	}
	void Add(int i){
		relax();
		int y=-inf, x=inf;
		if (X.size()) x=X.top().first;
		if (Y.size()) y=Y.top().first;
		if (A[i]<=x) mark[i]=2, Y.push({A[i], i});
		else mark[i]=1, X.push({A[i], i}), sum+=A[i], sz++;
	}
	void Rem(int i){
		if (mark[i]==1) sum-=A[i], sz--;
		mark[i]=0;
		relax(); // not necessary
	}
	ll Get(int k){
		if (k<0) return -INF;
		while (sz<k && Y.size()){
			int i=Y.top().second;
			Y.pop();
			if (mark[i]!=2) continue ;
			mark[i]=1;
			X.push({A[i], i});
			sum+=A[i];
			sz++;
		}
		while (sz>k){
			int i=X.top().second;
			X.pop();
			if (mark[i]!=1) continue ;
			mark[i]=2;
			Y.push({A[i], i});
			sum-=A[i];
			sz--;
		}
		return sum;
	}
} S;

inline void Move(int l, int r){
	while (L<l) S.Rem(L++);
	while (r<R) S.Rem(--R);
	while (l<L) S.Add(--L);
	while (R<r) S.Add(R++);
}
void divide(int tl, int tr, int optl, int optr){
	if (tr<tl) return ;
	int mid=(tl+tr)>>1, opt=-1;
	ll res=-INF-1;
	Move(mid, optl);
	for (int i=optl; i<=optr; i++){
		S.Add(R++);
		ll val=S.Get(D-2*(start-mid)-(i-start));
		if (val>res){
			res=val;
			opt=i;
		}
	}/*
	debug2(mid, opt)
	debug(res)
	cerr<<"\n";
	*/
	assert(opt!=-1);
	ans=max(ans, res);
	Move(tr, opt);
	divide(mid+1, tr, opt, optr);
	Move(mid-1, optl);
	divide(tl, mid-1, optl, opt);
}

ll findMaxAttraction(int nn, int starttt, int d, int attraction[]){
	n=nn;
	D=d;
	start=starttt;
	for (int i=0; i<n; i++) A[i]=attraction[i];
	L=R=start;
	divide(0, start, start, n-1);
//	debug(ans)
	
	
//	return ans;
	
	memset(S.mark, 0, sizeof(S.mark));
	S.relax();
	S.sum=S.sz=0;
	
	reverse(A, A+n);
	start=n-1-start;
	L=R=start;
	divide(0, start, start, n-1);
	
	return ans;
}
/*
5 2 7
10 2 20 30 1

5 2 7
1 30 20 2 10


*/

Compilation message

holiday.cpp: In member function 'void Set::Add(int)':
holiday.cpp:41:7: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   41 |   int y=-inf, x=inf;
      |       ^

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 6916 KB Output is correct
2 Correct 207 ms 6916 KB Output is correct
3 Correct 210 ms 6496 KB Output is correct
4 Correct 215 ms 6748 KB Output is correct
5 Correct 228 ms 10364 KB Output is correct
6 Correct 26 ms 3296 KB Output is correct
7 Correct 140 ms 5852 KB Output is correct
8 Correct 141 ms 6020 KB Output is correct
9 Correct 19 ms 3168 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1004 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 16 ms 1052 KB Output is correct
5 Correct 12 ms 1004 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 6 ms 748 KB Output is correct
8 Correct 5 ms 748 KB Output is correct
9 Correct 5 ms 748 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 4956 KB Output is correct
2 Correct 168 ms 10584 KB Output is correct
3 Correct 246 ms 3316 KB Output is correct
4 Correct 13 ms 876 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 5 ms 748 KB Output is correct
7 Correct 5 ms 748 KB Output is correct
8 Correct 924 ms 8284 KB Output is correct
9 Correct 933 ms 8208 KB Output is correct