Submission #569028

#	Time	Username	Problem	Language	Result	Execution time	Memory
569028		blue	MP3 Player (CEOI10_mp3player)	C++17	10 / 100	1095 ms	6244 KiB

mp3player

#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(int v1 = 0; v1 <= Vmax; v1++)
	{
		for(int y = 2; y <= N; y++)
		{
			int t = D[y]-1;

			// cerr << "\n\n";
			// cerr << t << ' ' << v1 << '\n';

			int cv = v1;
			for(int i = 1; i <= N; i++)
			{
				if(D[i] <= t)
					cv += A[i];

				cv = min(cv, Vmax);
				cv = max(cv, 0);
			}

			if(cv == V2)
			{
				if(t > T || (t == T && v1 > V1))
				{
					T = t;
					V1 = v1;
				}
			}
		}
	}

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

}

Compilation message (stderr)

mp3player.cpp: In function 'int main()':
mp3player.cpp:97:6: warning: unused variable 'u' [-Wunused-variable]
   97 |  int u = 0, v = 0;
      |      ^
mp3player.cpp:97:13: warning: unused variable 'v' [-Wunused-variable]
   97 |  int u = 0, v = 0;
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10