Submission #40460

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
40460	2018-02-01T19:53:28 Z	IvanC	Meteors (POI11_met)	C++14	100 / 100	3041 ms	65536 KB

#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
typedef long long ll;
struct pergunta{
	int ini,fim,meio,resp,id;
	pergunta(int _ini = 0,int _fim = 0){
		ini = _ini;
		fim = _fim;
		meio = -1;
		resp = -1;
	}
};
const int MAXN = 300010;
vector<int> estados[MAXN];
vector<pergunta> P;
ll bit[MAXN];
int N,M,K,li[MAXN],ri[MAXN],ai[MAXN],qtd[MAXN],maximom;
vector<int> bucket[MAXN];
void update_val(int idx,ll val){
	while(idx <= M + 1){
		bit[idx] += val;
		idx += LSOne(idx);
	}
}
void update(int a,int b,ll val){
	update_val(a,val);
	update_val(b+1,-val);
}
ll query(int idx){
	ll ans = 0;
	while(idx > 0){
		ans += bit[idx];
		idx -= LSOne(idx);
	}
	return ans;
}
void do_update(int i){
	if(li[i] <= ri[i]){
		update(li[i],ri[i],ai[i]);
	}
	else{
		update(li[i],M,ai[i]);
		update(1,ri[i],ai[i]);
	}
}
void checa(int i){
	ll tot = qtd[i];
	for(int j : estados[i]){
		tot -= query(j);
		if(tot <= 0) break;
	}
	if(tot <= 0){
		P[i].resp = P[i].meio;
		P[i].fim = P[i].meio - 1;
	}
	else{
		P[i].ini = P[i].meio + 1;
	}
}
int main(){
	pergunta dummy(0,0);
	P.push_back(dummy);
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=M;i++){
		int x;
		scanf("%d",&x);
		estados[x].push_back(i);
	}
	for(int i = 1;i<=N;i++) scanf("%d",&qtd[i]);
	scanf("%d",&K);
	for(int i = 1;i<=N;i++){
		pergunta davez(1,K);
		P.push_back(davez);
	}
	for(int i = 1;i<=K;i++){
		scanf("%d %d %d",&li[i],&ri[i],&ai[i]);
	}
	int limite = ceil(log(K)/log(2)) + 1;
	for(int iteracao = 1;iteracao<=limite;iteracao++){
		for(int i = 1;i<=M+1;i++) bit[i] = 0;
		maximom = 0;
		for(int i = 1;i<=N;i++){
			if(P[i].ini > P[i].fim){
				continue;
			}
			P[i].meio = (P[i].ini + P[i].fim)/2;
			maximom = max(P[i].meio,maximom);
			bucket[P[i].meio].push_back(i);
		}
		for(int atualizacao = 1;atualizacao<=maximom;atualizacao++){
			do_update(atualizacao);
			if(bucket[atualizacao].empty()) continue;
			while(!bucket[atualizacao].empty()){
				int i = bucket[atualizacao].back();
				bucket[atualizacao].pop_back();
				checa(i);
			}
		}
	}
	for(int i = 1;i<=N;i++){
		if(P[i].resp == -1) printf("NIE \n");
		else printf("%d\n",P[i].resp);
	}
	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:64:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
met.cpp:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^
met.cpp:70:45: 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",&qtd[i]);
                                             ^
met.cpp:71:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&K);
                ^
met.cpp:77:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&li[i],&ri[i],&ai[i]);
                                         ^

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	14456 KB	Output is correct
2	Correct	14 ms	14560 KB	Output is correct
3	Correct	13 ms	14612 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	14684 KB	Output is correct
2	Correct	13 ms	14740 KB	Output is correct
3	Correct	14 ms	14892 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	16572 KB	Output is correct
2	Correct	156 ms	18876 KB	Output is correct
3	Correct	174 ms	18876 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	140 ms	18876 KB	Output is correct
2	Correct	137 ms	18876 KB	Output is correct
3	Correct	157 ms	18932 KB	Output is correct
4	Correct	53 ms	18932 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	130 ms	18932 KB	Output is correct
2	Correct	129 ms	19472 KB	Output is correct
3	Correct	44 ms	19472 KB	Output is correct
4	Correct	144 ms	19472 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	19472 KB	Output is correct
2	Correct	137 ms	19472 KB	Output is correct
3	Correct	102 ms	19472 KB	Output is correct
4	Correct	160 ms	20276 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1446 ms	35396 KB	Output is correct
2	Correct	196 ms	35396 KB	Output is correct
3	Correct	190 ms	35396 KB	Output is correct
4	Correct	2386 ms	65536 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1582 ms	65536 KB	Output is correct
2	Correct	742 ms	65536 KB	Output is correct
3	Correct	96 ms	65536 KB	Output is correct
4	Correct	3041 ms	65536 KB	Output is correct