oj.uz

Submission #755010

# Submission time Handle Problem Language Result Execution time Memory
755010 2023-06-09T09:32:25 Z AngusRitossa Holiday (IOI14_holiday) C++14
24 / 100
 153 ms 41900 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int lef[1000010], righ[1000010], am[1000010];
ll val[1000010];
int upto;
void update(int node, int oldcurr, int curr, int cstart = 0, int cend = 1e9+10)
{
	if (cstart == cend)
	{
		am[curr] = am[oldcurr]+1;
		val[curr] = ((ll)am[curr]) * ((ll)cstart);
		return;
	}
	int mid = (cstart+cend)/2;
	if (node <= mid) 
	{
		lef[curr] = ++upto;
		righ[curr] = righ[oldcurr];
		update(node, lef[oldcurr], lef[curr], cstart, mid);
	}
	else
	{
		righ[curr] = ++upto;
		lef[curr] = lef[oldcurr];
		update(node, righ[oldcurr], righ[curr], mid+1, cend);
	}
	am[curr] = am[lef[curr]] + am[righ[curr]];
	val[curr] = val[lef[curr]] + val[righ[curr]];
}
ll query(int amt, int oldcurr, int curr, int cstart = 0, int cend = 1e9+10)
{
	if (amt >= am[curr] - am[oldcurr]) return val[curr] - val[oldcurr];
	else if (cstart == cend)
	{
		ll mult = min(amt, am[curr]-am[oldcurr]);
		return mult*(ll)cstart;
	}
	int mid = (cstart+cend)/2;
	if (am[righ[curr]] - am[righ[oldcurr]] >= amt)
	{
		return query(amt, righ[oldcurr], righ[curr], mid+1, cend);
	}
	else
	{
		int newam = amt - (am[righ[curr]] - am[righ[oldcurr]]);
		ll val2 = val[righ[curr]] - val[righ[oldcurr]];
		return val2 + query(newam, lef[oldcurr], lef[curr], cstart, mid);
	}
} 
int* rootat;
int otherarray[100010];
priority_queue<ll> pq;
ll mx;
ll findMaxAttraction2(int n, int start, int d, int attraction[]) {
    assert(!start);
    int at = d/2;
    int moves = at*2-1;
    ll sum = 0;
    for (int i = 0; i < at; i++)
    {
    	sum += attraction[i];
    	pq.push(-attraction[i]);
    }
    mx = sum;
    for (int i = at; i < n; i++)
    {
    	moves += 2;
    	pq.push(-attraction[i]);
    	sum += attraction[i];
    	while (moves > d && pq.size())
    	{
    		sum += pq.top();
    		pq.pop();
    		moves--;
    	}
    	//printf("%d %d\n", pq.size(), mx);
    	mx = max(mx, sum);
    }
    return mx;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	rootat = otherarray+1;
	if (!start) return findMaxAttraction2(n, start, d, attraction);
	for (int i = 0; i < n; i++)
	{
		rootat[i] = ++upto;
		update(attraction[i], rootat[i-1], rootat[i]);
	}
    for (int s = 0; s <= start; s++)
    {
    	int dist = start-s-1;
    	for (int e = s; e < n; e++)
    	{
    		dist++;
    		int allowed = d-dist;
    		if (allowed <= 0) continue;
    		ll sum = query(allowed, rootat[s-1], rootat[e]);
    		mx = max(mx, sum);
    	}
    }
   // printf("\n");
    for (int e = start; e < n; e++)
    {
    	int dist = e-start-1;
    	for (int s = e; s >= 0; s--)
    	{
    		dist++;
    		int allowed = d-dist;
    		if (allowed <= 0) continue; 
    		ll sum = query(allowed, rootat[s-1], rootat[e]);
    		mx = max(mx, sum);
    	}
    }
    return mx;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1996 KB Output is correct
2 Correct 8 ms 1996 KB Output is correct
3 Correct 8 ms 1984 KB Output is correct
4 Correct 8 ms 1996 KB Output is correct
5 Correct 17 ms 1600 KB Output is correct
6 Correct 4 ms 1856 KB Output is correct
7 Correct 8 ms 1432 KB Output is correct
8 Correct 11 ms 1488 KB Output is correct
9 Runtime error 6 ms 3056 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2576 KB Output is correct
2 Correct 36 ms 2516 KB Output is correct
3 Correct 33 ms 2564 KB Output is correct
4 Correct 153 ms 2456 KB Output is correct
5 Correct 105 ms 2260 KB Output is correct
6 Correct 7 ms 1312 KB Output is correct
7 Correct 16 ms 1332 KB Output is correct
8 Correct 18 ms 1236 KB Output is correct
9 Correct 21 ms 1336 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 41900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -