Submission #571932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571932	2022-06-03T07:45:02 Z	blue	Santa Claus (RMI19_santa)	C++17	0 / 100	249 ms	13396 KB

santa

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
const int mx = 100'000;
 
using vi = vector<int>;
using pii = pair<int, int>;
 
struct segtree
{
	vi l = vi((1<<18) + 1);
	vi r = vi((1<<18) + 1);
 
	vi mn = vi((1<<18) + 1, 0); //change to long long if error
	vi lp = vi((1<<18) + 1, 0);
 
	void build(int i, int L, int R)
	{
		l[i] = L;
		r[i] = R;
 
		mn[i] = lp[i] = 0;
 
		if(l[i] == r[i])
			return;
 
		int m = (l[i] + r[i])/2;
		build(2*i, l[i], m);
		build(2*i+1, m+1, r[i]);
	}
 
	void add(int i, int L, int R, int V)
	{
		if(r[i] < L || R < l[i])
			return;
 
		// cerr << "add " << i << ' ' << l[i] << ' ' << r[i] << " : " << L << ' ' << R << ' ' << V << '\n'; 
 
		if(L <= l[i] && r[i] <= R)
		{
			lp[i] += V;
			mn[i] += V;
		}
		else
		{
			add(2*i, L, R, V);
			add(2*i+1, L, R, V);
			mn[i] = lp[i] + min(mn[2*i], mn[2*i+1]);
		}
	}
 
	int rangemin(int i, int L, int R)
	{
		// cerr << "rangemin " << i << ' ' << l[i] << ' ' << r[i] << " : " << L << ' ' << R << '\n';
		if(r[i] < L || R < l[i])
		{
			// cerr << "case 1\n";
			return 1'000'000'000;
		}
		else if(L <= l[i] && r[i] <= R)
		{
			// cerr << "case 2\n";
			return mn[i];
		}
		else
		{
			// cerr << "case 3\n";
			return lp[i] + min(rangemin(2*i, L, R), rangemin(2*i+1, L, R));
		}
	}
};
 
int N;
 
segtree S;
 
vi X, H, V;
 
multiset<int> elves, children;
 
void output()
{
	for(int i = 0; i <= N; i++)
		cerr << S.rangemin(1, i, i) << ' ';
	cerr << '\n';
}
 
void addelf(int i)
{
	// cerr << "add elf " << i << '\n';
	// elves.insert(i);
	S.add(1, i, N, -1);
 
	// output();
}
 
void removeelf(int i)
{
	// cerr << "remove elf " << i << '\n';
	// elves.erase(elves.find(i));
	S.add(1, i, N, +1);
 
	// output();
}
 
void addchild(int i)
{
	// cerr << "pre : " << S.rangemin(1, 0, 0) << '\n';
	// cerr << "add child " << i << '\n';
	// children.insert(i);
	S.add(1, i, N, +1);
 
	// output();
 
	// cerr << "post : " << S.rangemin(1, 0, 0) << '\n';
}
 
void removechild(int i)
{
	// cerr << "remove child " << i << '\n';
	// children.erase(children.find(i));
	S.add(1, i, N, -1);
 
	// output();
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int T;
	cin >> T;
 
	for(int t = 1; t <= T; t++)
	{
		cin >> N;
 
		S.build(1, 0, N); //could bad values be accessed from previous tests? check if WA
 
		// cerr << "pre pre : " << S.rangemin(1, 0, 0) << '\n';
 
		// output();
 
		X = H = V = vi(1+N);
 
		int maxelf = 0;
 
		for(int i = 1; i <= N; i++)
			cin >> X[i];
 
		for(int i = 1; i <= N; i++)
		{
			cin >> H[i];
			if(H[i] == 0)
				maxelf = max(maxelf, i);
		}
 
		for(int i = 1; i <= N; i++)
			cin >> V[i];
 
		vi D(1+N, -1);
 
		int jm = 0; //J - 1
 
		set<pii> gifts; 
 
		// cerr << "Maxelf = " << maxelf << '\n';
 
		vi remgift(1+N, -1);
 
		for(int i = 0; i <= N; i++)
		{
			// cerr << "i = " << i << '\n';
			// cerr << H[i] << '\n';
			if(i >= 1)
			{
				if(H[i] == 0) //elf
				{
					// newgift[i].push_back(i);
					gifts.insert({V[i], i});
					// cerr << "adding elf : " << i << '\n';
					addelf(V[i]);
				}
				else //child
				{
					auto it = gifts.lower_bound({V[i], -1});
					if(it != gifts.end())
					{
						remgift[i] = it->second;
						gifts.erase(it);
						// cerr << "removing elf : " << remgift[i] << '\n';
						removeelf(V[remgift[i]]);
					}
				}
			}
		}

		int ii = N;
 
 
		// for(int i = N-1; i >= 0; i--)
		for(int i2 = N; i2 >= maxelf; i2--)
		{
			// for(int i2 = i+1; i2 <= N; i2++)
 
			// for(int z = i2+1; z <= N; z++)
			// {
			if(i2 < N)
			{
				if(H[i2+1] == 0)
					removeelf(V[i2+1]);
				else if(remgift[i2+1] >= 1)
					addelf(V[remgift[i2+1]]);
			}
				
			// }

			// cerr << "hello\n";

			while((S.mn[1] < 0 && ii-1 >= 0) || ii >= i2)
			{
				ii--;
				if(H[ii+1] == 1)
				{

					addchild(V[ii+1]);
					if(remgift[ii+1] >= 1)
						addelf(V[remgift[ii+1]]);
				}
			}
			// cerr << "A\n";
			if(S.mn[1] >= 0)
			{
				// ilo = i;
				// cerr << i2 << ' ' << ii << '\n';
				if(D[i2] == -1 || X[i2] + (X[i2] - X[ii+1]) < D[i2])
					D[i2] = X[i2] + (X[i2] - X[ii+1]);
				// break;
			}
			// cerr << "done\n";
 
			// int ilo;
 
			// for(int i = i2-1; i >= 0; i--)
			// {
 
			// 	if(H[i+1] == 1)
			// 	{
			// 		addchild(V[i+1]);
			// 		if(remgift[i+1] >= 1)
			// 			addelf(V[remgift[i+1]]);
			// 	}
 
 
			// 	// if(i2 >= maxelf)
					
			// }
 
			// for(int u = ilo; u < i2; u++)
			// {
			// 	if(H[u+1] == 0)
			// 	{
			// 		// removeelf(V[u]);
			// 		// addelf(V[u]);
			// 		;
			// 	}
			// 	else 
			// 	{
			// 		removechild(V[u+1]);
 
			// 		if(remgift[u+1] >= 1)
			// 		removeelf(V[remgift[u+1]]);
			// 	}
			// }
		}
 
 
 
		for(int i = 1; i <= N; i++)
			cout << D[i] << ' ';
		cout << '\n';
	}
}

Compilation message

santa.cpp: In function 'int main()':
santa.cpp:166:7: warning: unused variable 'jm' [-Wunused-variable]
  166 |   int jm = 0; //J - 1
      |       ^~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	4436 KB	Output isn't correct
2	Incorrect	4 ms	4436 KB	Output isn't correct
3	Incorrect	9 ms	4520 KB	Output isn't correct
4	Incorrect	18 ms	4584 KB	Output isn't correct
5	Incorrect	37 ms	5276 KB	Output isn't correct
6	Incorrect	46 ms	5880 KB	Output isn't correct
7	Incorrect	89 ms	7564 KB	Output isn't correct
8	Incorrect	128 ms	9300 KB	Output isn't correct
9	Incorrect	175 ms	10368 KB	Output isn't correct
10	Incorrect	249 ms	13396 KB	Output isn't correct