oj.uz

Submission #569042

# Submission time Handle Problem Language Result Execution time Memory
569042 2022-05-26T14:01:54 Z blue MP3 Player (CEOI10_mp3player) C++17
100 / 100
 98 ms 6348 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

int N, Vmax, V2;
vi A, C;
vi D;

const int INF = 2'000'000'005;


struct func
{
	int y1;
	int x1;
	int x2;

	int eval(int x)
	{
		if(x <= x1)
			return y1;
		else
			return y1 + min(x,x2) - x1;
	}
};

func combine(func A, func B)
{
	if(max(A.y1, B.x1) <= min(A.y1 + A.x2 - A.x1, B.x2))
		return {B.eval(A.eval(0)), max(A.y1, B.x1) - A.y1 + A.x1, min(A.y1 + A.x2 - A.x1, B.x2) - A.y1 + A.x1};
	else
		return {B.eval(A.eval(0)), 0, 0};
}

func nothing;
func plusone;
func minusone;

const int lg = 17;
const int Z = (1<<lg);




vector<func> segtree;

void set(int i, func v)
{
	segtree[Z+i] = v;
	for(int j = (Z+i)>>1; j >= 1; j >>= 1)
		segtree[j] = combine(segtree[2*j], segtree[2*j+1]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> Vmax >> V2;

	nothing = {0, 0, Vmax};
	plusone = {1, 0, Vmax-1};
	minusone = {0, 1, Vmax};

	A = C = vi(1+N);

	for(int i = 1; i <= N; i++)
	{
		char c;
		cin >> c;
		A[i] = (c == '+' ? +1 : -1);
		cin >> C[i];
	}

	D = vi(1+N);
	D[1] = INF;
	for(int i = 2; i <= N; i++)
		D[i] = C[i] - C[i-1];

	vi I;
	for(int i = 1; i <= N; i++)
		I.push_back(i);


	int T = 0, V1 = V2;

	sort(I.begin(), I.end(), [] (int p, int q)
	{
		return D[p] < D[q];
	});

	int u = 0, v = 0;

	segtree = vector<func>((1<<(lg+1)) + 1, nothing);

	for(u = 0; u < N; u++)
	{
		
		int currlim = D[I[u]] - 1;
		// cerr << "checking : " << currlim << '\n';
		int y1 = segtree[1].y1, x1 = segtree[1].x1, x2 = segtree[1].x2;
		int y2 = y1+x2-x1;

		// cerr << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << '\n';


		if(y1 <= V2 && V2 <= y2)
		{
			// cerr << "equal? " << V2 << " : " << y2 << '\n';
			// cerr << Vmax << '\n';

			// cerr << "y2 = " << 

			int currV1 = (y2 == V2 ? Vmax : V2-y1+x1);

			cerr << currV1 << '\n';

			// cerr << "option: " << currV1 << ' ' << currlim << '\n';

			if(currlim > T || (currlim == T && currV1 > V1))
			{
				T = currlim;
				V1 = currV1;
			}
		}


		// cerr << u << " : " << currlim << '\n';

		for(v = u; v < N && D[I[v]] == D[I[u]]; v++)
		{
			int i = I[v];

			if(i != 1)
			{
				if(A[i] == +1)
				set(i, plusone);
				else
					set(i, minusone);
			}

			// cerr << "activating : " << i << '\n';
		}

		u = v-1;


		
	}

	if(T > 2'000'000'000)
		cout << "infinity\n";
	else
		cout << T << ' ' << V1 << '\n';

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 5 ms 3404 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3412 KB Output is correct
2 Correct 4 ms 3540 KB Output is correct
3 Correct 4 ms 3532 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3796 KB Output is correct
2 Correct 18 ms 3796 KB Output is correct
3 Correct 13 ms 3796 KB Output is correct
4 Correct 12 ms 4044 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3924 KB Output is correct
2 Correct 15 ms 3924 KB Output is correct
3 Correct 13 ms 3924 KB Output is correct
4 Correct 12 ms 4052 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3924 KB Output is correct
2 Correct 33 ms 4024 KB Output is correct
3 Correct 18 ms 4056 KB Output is correct
4 Correct 11 ms 3924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4144 KB Output is correct
2 Correct 24 ms 4184 KB Output is correct
3 Correct 17 ms 4184 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5116 KB Output is correct
2 Correct 52 ms 6332 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 5132 KB Output is correct
2 Correct 44 ms 6348 KB Output is correct