oj.uz

Submission #586832

# Submission time Handle Problem Language Result Execution time Memory
586832 2022-06-30T17:59:50 Z Red_Inside Holiday (IOI14_holiday) C++17
100 / 100
 456 ms 8028 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define IOS ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define all(v) v.begin(), v.end()

const int maxn = 1e5+100;

//#define int ll
#define pii pair <int, int>
ll inf = 1e18;

ll n, m, ukl, ukr, d, ts[4*maxn], tc[4*maxn], pos[maxn], a[maxn], res = -inf;
pair <ll, int> b[maxn];

void upd(int v, int tl, int tr, int pos, ll val)
{
//	if(v == 1) cout << "UPDATE " << pos << " " << val << endl;
	if(pos < tl || tr < pos) return;
	if(tl == tr)
	{
		ts[v] += val;
		if(ts[v] > 0) tc[v]++;
		else tc[v]--;
		return;
	}
	upd(v * 2, tl, (tl + tr) / 2, pos, val);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val);
	ts[v] = ts[v * 2] + ts[v * 2 + 1];
	tc[v] = tc[v * 2] + tc[v * 2 + 1];
}

ll get(int v, int tl, int tr, int k)
{
	if(tl == tr)
	{
		return ts[v];
	}
	if(tc[v * 2 + 1] >= k) return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, k);
	else return get(v * 2, tl, (tl + tr) / 2, k - tc[v * 2 + 1]) + ts[v * 2 + 1];
}

void print(int v, int tl, int tr)
{
	if(tl == tr)
	{
		cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl;
		return;
	}
	print(v * 2, tl, (tl + tr) / 2);
	cout << tl << " " << tr << " " << ts[v] << " " << tc[v] << endl;
	print(v * 2 + 1, (tl + tr) / 2 + 1, tr);
}

void solve(int l, int r, int optl = m, int optr = n)
{
	if(l > r) return;
	int mid = (l + r) / 2;
	while(ukl > mid)
	{
		ukl--;
		upd(1, 1, n, pos[ukl], a[ukl]);
	}
	while(ukl < mid)
	{
		upd(1, 1, n, pos[ukl], -a[ukl]);
		ukl++;
	}
	ll ans = -inf;
	int opt;
	forn(optl, i, optr)
	{
		while(ukr < i)
		{
			ukr++;
			upd(1, 1, n, pos[ukr], a[ukr]);
		}
		while(ukr > i)
		{
			upd(1, 1, n, pos[ukr], -a[ukr]);
			ukr--;
		}
		//m-mid
		//i-m
//		cout << "FOR " << mid << " " << i << " " << d-(i-mid+min(i-m, m-mid)) << " " << get(1, 1, n, d-(i-mid+min(i-m, m-mid))) << " " << ukl << " " << ukr << endl;
//		print(1, 1, n);
		ll temp = get(1, 1, n, d-(i-mid+min(i-m, m-mid)));
		res = max(res, temp);
		if(temp > ans)
		{
			ans = temp;
			opt = i;
		}
	}
//	cout << mid << " " << opt << endl;
	solve(l, mid-1, optl, opt);
	solve(mid+1, r, opt, optr);
}

long long int findMaxAttraction(int N, int start, int D, int attraction[]) 
{
	n = N;
	d = D;
	forn(1, i, n)
	{
		b[i].f = attraction[i-1];
		b[i].s = i;
		a[i] = b[i].f;
	}
	sort(b + 1, b + 1 + n);
	forn(1, i, n)
	{
		pos[b[i].s] = i;
	}
	start++;
	m = start;
	ukr = start;
	ukl = start;
	upd(1, 1, n, pos[start], a[start]);
	solve(1, start);
	return res;
}

Compilation message

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:102:7: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |  solve(l, mid-1, optl, opt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7868 KB Output is correct
2 Correct 32 ms 7844 KB Output is correct
3 Correct 34 ms 7908 KB Output is correct
4 Correct 33 ms 7940 KB Output is correct
5 Correct 47 ms 7596 KB Output is correct
6 Correct 16 ms 2628 KB Output is correct
7 Correct 23 ms 4308 KB Output is correct
8 Correct 27 ms 4708 KB Output is correct
9 Correct 8 ms 2260 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 6 ms 944 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 784 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 7920 KB Output is correct
2 Correct 39 ms 7812 KB Output is correct
3 Correct 152 ms 4156 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 456 ms 8028 KB Output is correct
9 Correct 436 ms 8028 KB Output is correct