Submission #218013

#	Time	Username	Problem	Language	Result	Execution time	Memory
218013		tincamatei	Santa Claus (RMI19_santa)	C++14	100 / 100	647 ms	12920 KiB

santa

/**
* user:  tinca-6db
* fname: Matei
* lname: Tinca
* task:  santa
* score: 100.0
* date:  2019-10-11 10:35:45.784954
*/
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
const int INF = 1000000000;

int aint[1+4*(MAX_N+1)], lazy[1+4*(MAX_N+1)];

void pushlazy(int l, int r, int nod) {
	aint[nod] += lazy[nod];
	if(l < r) {
		lazy[2 * nod] += lazy[nod];
		lazy[2 * nod + 1] += lazy[nod];
	}
	lazy[nod] = 0;
}

void update(int i, int j, int val, int l = 0, int r = MAX_N, int nod = 1) {
	pushlazy(l, r, nod);
	if(j < l || r < i || j < i) return;

	if(i <= l && r <= j) {
		lazy[nod] += val;
		pushlazy(l, r, nod);
	} else {
		int mid = (l + r) / 2;
		update(i, j, val, l, mid, 2 * nod);
		update(i, j, val, mid + 1, r, 2 * nod + 1);
		aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
	}
} 

int query(int i, int j, int l = 0, int r = MAX_N, int nod = 1) {
	pushlazy(l, r, nod);
	if(r < i || j < l || j < i) return INF;

	if(i <= l && r <= j)
		return aint[nod];
	else {
		int mid = (l + r) / 2;
		return min(query(i, j, l, mid, 2 * nod),
		           query(i, j, mid + 1, r, 2 * nod + 1));
	}
}

void initaint(int nod = 1, int l = 0, int r = MAX_N) {
	aint[nod] = lazy[nod] = 0;
	if(l < r) {
		int mid = (l + r) / 2;
		initaint(2 * nod, l, mid);
		initaint(2 * nod + 1, mid + 1, r);
	}
}

int x[1+MAX_N], h[1+MAX_N], v[1+MAX_N];

void debugAint(int N) {
	printf("Aint: ");
	for(int i = 0; i <= N; ++i)
		printf("%d ", query(i, i));
	printf("\n");
}

void solvetest() {
	int N, lastElf = 0;
	initaint();
	
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
		scanf("%d", &x[i]);
	for(int i = 1; i <= N; ++i) {
		scanf("%d", &h[i]);
		if(h[i] == 0)
			lastElf = i;
	}
	for(int i = 1; i <= N; ++i)
		scanf("%d", &v[i]);
	
	if(lastElf == 0) {
		for(int i = 1; i <= N; ++i)
			printf("%d ", x[i]);
		printf("\n");
		return;
	}

	int t = 0;
	while(t <= N && (t < lastElf || query(0, MAX_N) < 0)) {
		if(t > 0)
			printf("-1 ");
		++t;
		if(h[t] == 0)
			update(v[t], MAX_N, -1);
		else
			update(v[t], MAX_N, 1);
	}

	initaint();
	for(int i = 1; i <= t; ++i) {
		if(h[i] == 0)
			update(v[i], MAX_N, -1);
		else
			update(v[i], MAX_N, 1);
	}
	// de la t este posibil sa faci alea alea
	int left = 0; // prima locatie la care NU MA MAI INTORC
	set<pair<int, int> > gifts;
	for(int i = t; i <= N; ++i) {
		// muta pointer
		bool ok;
		do {
			ok = false;
			if(left + 1 < i) {
				if(h[left + 1] == 1) { // copil
					update(v[left + 1], MAX_N, - 1);

					set<pair<int, int> >::iterator it = gifts.lower_bound({v[left + 1], -1});
					if(it != gifts.end()) { // ii dam copilului pe care tocmai l-am scos un cadou cat mai prost
						update(it->first, MAX_N, 1);
						/*if(query(0, MAX_N) >= 0) {
							gifts.erase(it);
							++left;
						} else {
							update(v[left + 1], MAX_N, 1);
							update(it->first, MAX_N, -1);
						}*/
					}

					if(query(0, MAX_N) >= 0) {
						if(it != gifts.end())
							gifts.erase(it);
						++left;
						ok = true;
					} else {
						update(v[left + 1], MAX_N, 1);
						if(it != gifts.end())
							update(it->first, MAX_N, -1);
					}
				} else {
					gifts.insert({v[left + 1], left + 1});
					++left;
					ok = true;
				}
			}
		} while(ok);
		
		if(i + 1 <= N)
			update(v[i + 1], MAX_N, 1);

		printf("%d ", 2 * x[i] - x[left + 1]);
	}
	printf("\n");
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--)
		solvetest();
	return 0;
}

Compilation message (stderr)

santa.cpp: In function 'void solvetest()':
santa.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
santa.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x[i]);
   ~~~~~^~~~~~~~~~~~~
santa.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &h[i]);
   ~~~~~^~~~~~~~~~~~~
santa.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~
santa.cpp: In function 'int main()':
santa.cpp:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &T);
  ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100