Submission #198574

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
198574	2020-01-26T16:45:53 Z	Akashi	Santa Claus (RMI19_santa)	C++14	100 / 100	466 ms	14072 KB

santa

#include <bits/stdc++.h>
using namespace std;

const int SZ = 1e5 + 5;

int n, t;
int ans[SZ], x[SZ], v[SZ];
bool h[SZ];
multiset <int> s;
int Arb[SZ * 4], Lazy[SZ * 4];

void propag(int nod){
	if(!Lazy[nod]) return ;
	for(int i = nod * 2; i <= nod * 2 + 1 ; ++i){
		Lazy[i] += Lazy[nod];
		Arb[i] += Lazy[nod];
	}
	Lazy[nod] = 0;
}

void add(int x, int y, int val, int st = 1, int dr = n, int nod = 1){
	if(x <= st && dr <= y){
		Lazy[nod] += val;
		Arb[nod] += val;
		return ;
	}
	propag(nod);
	
	int mij = (st + dr) / 2;
	if(x <= mij) add(x, y, val, st, mij, nod * 2);
	if(mij + 1 <= y) add(x, y, val, mij + 1, dr, nod * 2 + 1);
	
	Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}

int main(){
	//freopen("1.in", "r", stdin);
	
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		for(int i = 1; i <= n ; ++i) scanf("%d", &x[i]);
		
		int Last_elf = 0;
		for(int i = 1; i <= n ; ++i){
			scanf("%d", &h[i]);
			ans[i] = -1;
			if(!h[i]) Last_elf = i;
		}
		for(int i = 1; i <= n ; ++i) scanf("%d", &v[i]);
	
		memset(Arb, 0, sizeof(Arb));
		memset(Lazy, 0, sizeof(Lazy));

		int j = 1;
		while(j <= Last_elf){
			if(h[j]) add(v[j], n, 1);
			else add(v[j], n, -1);
			++j;
		}		
		
		s.clear();
		for(int st = 1; st <= n ; ++st){
			if(j == st) add(v[j], n, 1), ++j;
			while(Arb[1] < 0 && j <= n){
				add(v[j], n, 1);
				++j;
			}
			
			if(Arb[1] >= 0) ans[j - 1] = st;
			
			if(h[st]){
				multiset <int> :: iterator it = s.lower_bound(v[st]);
				if(it != s.end()){
					add(*it, n, 1);
					s.erase(it);
				}
				add(v[st], n, -1);
			}
			else s.insert(v[st]);
		}
		
		ans[0] = -1;
		for(int i = Last_elf + 1; i <= n ; ++i)
			ans[i] = max(ans[i], ans[i - 1]);
	
		for(int i = 1; i <= n ; ++i){
			if(ans[i] == -1) printf("%d ", ans[i]);
			else printf("%d ", 2 * x[i] - x[ans[i]]);
		}
		printf("\n");
	}
	return 0;
}

Compilation message

santa.cpp: In function 'int main()':
santa.cpp:46:21: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
    scanf("%d", &h[i]);
                ~~~~~^
santa.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
santa.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
santa.cpp:42:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= n ; ++i) scanf("%d", &x[i]);
                                ~~~~~^~~~~~~~~~~~~
santa.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &h[i]);
    ~~~~~^~~~~~~~~~~~~
santa.cpp:50:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= n ; ++i) scanf("%d", &v[i]);
                                ~~~~~^~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3452 KB	Output is correct
2	Correct	9 ms	3448 KB	Output is correct
3	Correct	23 ms	3704 KB	Output is correct
4	Correct	33 ms	3960 KB	Output is correct
5	Correct	66 ms	4600 KB	Output is correct
6	Correct	101 ms	5496 KB	Output is correct
7	Correct	166 ms	7160 KB	Output is correct
8	Correct	256 ms	8952 KB	Output is correct
9	Correct	319 ms	11128 KB	Output is correct
10	Correct	466 ms	14072 KB	Output is correct