oj.uz

Submission #40418

# Submission time Handle Problem Language Result Execution time Memory
40418 2018-02-01T12:30:02 Z IvanC Meteors (POI11_met) C++14
74 / 100
 6000 ms 34804 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pergunta{
	int ini,fim,meio,resp,id;
	pergunta(int _ini = 0,int _fim = 0,int _id = 0){
		ini = _ini;
		fim = _fim;
		id = _id;
		meio = -1;
		resp = -1;
	}
	bool operator<(const pergunta &other)const{
		return meio < other.meio;
	}
};
const int MAXN = 300010;
vector<int> estados[MAXN];
vector<pergunta> P;
ll seg[4*MAXN],lazy[4*MAXN];
int N,M,K,li[MAXN],ri[MAXN],ai[MAXN],qtd[MAXN];
void propagate(int pos,int left,int right){
	seg[pos] += lazy[pos];
	if(left != right){
		lazy[2*pos] += lazy[pos];
		lazy[2*pos+1] += lazy[pos];
	}
	lazy[pos] = 0;
}
void build(int pos,int left,int right){
	seg[pos] = lazy[pos] = 0;
	if(left == right) return;
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
}
void update(int pos,int left,int right,int i,int j,ll val){
	propagate(pos,left,right);
	if(left > right || left > j || right < i) return;
	if(left >= i && right <= j){
		lazy[pos] += val;
		propagate(pos,left,right);
		return;
	}
	int mid = (left+right)/2;
	update(2*pos,left,mid,i,j,val);
	update(2*pos+1,mid+1,right,i,j,val);
}
ll query(int pos,int left,int right,int x){
	propagate(pos,left,right);
	if(left == right) return seg[pos];
	int mid = (left+right)/2;
	if(x <= mid) return query(2*pos,left,mid,x);
	else return query(2*pos+1,mid+1,right,x);
}
void do_update(int i){
	if(li[i] <= ri[i]){
		update(1,1,M,li[i],ri[i],ai[i]);
	}
	else{
		update(1,1,M,li[i],M,ai[i]);
		update(1,1,M,1,ri[i],ai[i]);
	}
}
int main(){
	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,i);
		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++){
		build(1,1,M);
		for(int i = 0;i<N;i++){
			if(P[i].ini > P[i].fim) P[i].meio = -1;
			P[i].meio = (P[i].ini + P[i].fim)/2;
		}
		sort(P.begin(),P.end());
		int atualizacao = 1;
		for(int i = 0;i<N;i++){
			if(P[i].meio == -1) continue;
			while(atualizacao <= P[i].meio){
				do_update(atualizacao);
				atualizacao++;
			}
			ll tot = qtd[P[i].id];
			for(int j : estados[P[i].id]){
				tot -= query(1,1,M,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;
			}
		}
	}
	for(int i = 0;i<N;i++){
		qtd[P[i].id] = P[i].resp; 
	}
	for(int i = 1;i<=N;i++){
		if(qtd[i] == -1) printf("NIE\n");
		else printf("%d\n",qtd[i]);
	}
	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:66: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:69:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^
met.cpp:72: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:73:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&K);
                ^
met.cpp:79: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 11 ms 7416 KB Output is correct
2 Correct 12 ms 7536 KB Output is correct
3 Correct 13 ms 7628 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7644 KB Output is correct
2 Correct 11 ms 7664 KB Output is correct
3 Correct 13 ms 7704 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 11784 KB Output is correct
2 Correct 850 ms 12776 KB Output is correct
3 Correct 756 ms 12776 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 12776 KB Output is correct
2 Correct 663 ms 12776 KB Output is correct
3 Correct 690 ms 12868 KB Output is correct
4 Correct 151 ms 12868 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 12868 KB Output is correct
2 Correct 662 ms 13000 KB Output is correct
3 Correct 122 ms 13000 KB Output is correct
4 Correct 691 ms 13000 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 13000 KB Output is correct
2 Correct 609 ms 13000 KB Output is correct
3 Correct 675 ms 13000 KB Output is correct
4 Correct 726 ms 13004 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6100 ms 34804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6038 ms 34804 KB Time limit exceeded
2 Halted 0 ms 0 KB -