oj.uz

Submission #586686

# Submission time Handle Problem Language Result Execution time Memory
586686 2022-06-30T14:35:34 Z Tekor Holiday (IOI14_holiday) C++17
100 / 100
 425 ms 7756 KB 
#include"holiday.h"

#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define ll long long
#define pll pair <ll,ll>
const int N = 3e5 + 100;
ll t[N * 4],sum;
int t1[N * 4],p[N],c[N];
void upd(int v,int tl,int tr,int pos,ll x) {
	if(tl == tr) {
		if(x == 0) {
			t1[v] = 0;
			t[v] = 0;
			return;
		}
		t1[v] = 1;
		t[v] = x;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)upd(v + v,tl,tm,pos,x);
	else upd(v + v + 1,tm + 1,tr,pos,x);
	t[v] = t[v + v] + t[v + v + 1];
	t1[v] = t1[v + v] + t1[v + v + 1];
}
ll get(int v,int tl,int tr,int x) {
	if(tl == tr)return t[v];
	int tm = (tl + tr) / 2;
	if(t1[v + v] >= x)return get(v + v,tl,tm,x);
	return get(v + v + 1,tm + 1,tr,x - t1[v + v]) + t[v + v];
}
int L,R,d,st,n;
ll ans;
void add(int x) {
	upd(1,0,n - 1,p[x],c[x]);
}
void del(int x) {
	upd(1,0,n - 1,p[x],0);
}
/*
5 2 7
10 2 20 30 1

*/
void calc(int l,int r,int optL,int optR) {
	if(l > r)return;
	int mid = (l + r) / 2;
	for(int i = L - 1;i >= mid;i--)add(i);
	for(int i = L;i < mid;i++)del(i);
	for(int i = R + 1;i <= optL;i++)add(i);
	for(int i = R;i > optL;i--)del(i);
	pair <ll,int> mx = mp(0,optL);
	R = optR;
	L = mid;
	for(int j = optL;j <= optR;j++) {
		if(j > optL)add(j);
		int kol = d - min(st - mid + j - mid,j - st + j - mid);
		if(mid == 0 && j == 3) {
		    //cout << kol << endl;
		}
		if(kol > 0)mx = max(mx,mp(get(1,0,n - 1,kol),j));
	}
	ans = max(ans,mx.f);
	//cout << mid << " " << mx.f << " " << mx.s << endl;
	if(l == r)return;
	calc(l,mid - 1,optL,mx.s);
	calc(mid + 1,r,mx.s,optR);
}
long long int findMaxAttraction(int NN, int start, int day, int a[]) {
	d = day;
	L = start + 1;
	R = start;
	st = start;
	n = NN;
	pii b[N];
	for(int i = 0;i < n;i++) {
		b[i] = mp(a[i],i);
		c[i] = a[i];
	}
	sort(b,b + n);
	reverse(b,b + n);
	for(int i = 0;i < n;i++) {
		p[b[i].s] = i;
	}
	calc(0,st,st,n - 1);
	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6884 KB Output is correct
2 Correct 25 ms 7028 KB Output is correct
3 Correct 44 ms 7000 KB Output is correct
4 Correct 25 ms 7032 KB Output is correct
5 Correct 40 ms 7096 KB Output is correct
6 Correct 17 ms 3924 KB Output is correct
7 Correct 22 ms 4948 KB Output is correct
8 Correct 27 ms 5076 KB Output is correct
9 Correct 8 ms 3984 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3156 KB Output is correct
2 Correct 3 ms 3156 KB Output is correct
3 Correct 3 ms 3156 KB Output is correct
4 Correct 8 ms 3188 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 3 ms 3028 KB Output is correct
9 Correct 4 ms 3028 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6856 KB Output is correct
2 Correct 32 ms 7756 KB Output is correct
3 Correct 120 ms 5328 KB Output is correct
4 Correct 7 ms 3156 KB Output is correct
5 Correct 4 ms 3096 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 4 ms 3028 KB Output is correct
8 Correct 419 ms 7732 KB Output is correct
9 Correct 425 ms 7724 KB Output is correct