Submission #41305

#	Time	Username	Problem	Language	Result	Execution time	Memory
41305		wzy	Meteors (POI11_met)	C++11	74 / 100	1654 ms	35008 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
int n ,m , k , ans[300005]   , l[300005] , r[300005] ;
long long bit[300005],  qt[300005];
vector<int> own[300005];
vector<int> sweep[300005];
pair<pii , int> querys[300005];

void upd(int x , int v){
	for(int i = x ; i < 300005; i += (i&-i)){
		bit[i] += v;
	}
	return;
}

long long gt(int x){
	int s = 0;
	for(int i = x ; i > 0 ; i -=(i&-i)){
		s+= bit[i];
	}
	return s;
}



void update(int l , int r , int v){
	if(l <= r){
		upd(l , v);
		upd(r + 1 , -v);
	}
	else{
		upd(l , v);
		upd(1 , v);
		upd(r + 1 , -v);
	}
	return;
}

long long query(int x){
	return gt(x);
}

int main(){
	scanf("%d%d" , &n , &m);
	for(int i = 1 ; i <= m;i++){
		int x;
		scanf("%d" , &x);
		own[x].pb(i);
	}
	for(int i = 1 ; i  <= n;i++) scanf("%lld" , &qt[i]);
	scanf("%d" , &k);
	for(int i = 1 ; i <= k ; i++){
		scanf("%d%d%d" , &querys[i].F.F , &querys[i].F.S , &querys[i].S);
	}
	for(int i = 1 ; i <= n;i++) l[i] = 1 , r[i] = k , ans[i] = -1;
	while(true){
		bool cabou = true;
		for(int i = 1 ; i <= n; i++){
			if(l[i] <= r[i]){
				sweep[(l[i] + r[i])/2].pb(i);
				cabou = false;
			}
		}
		if(cabou) break;
		for(int i = 1 ; i <= m + 1 ; i++) bit[i] = 0LL;
		for(int i = 1 ; i <= k ; i++){
			update(querys[i].F.F , querys[i].F.S , querys[i].S);
			while(sweep[i].size()){
				int u = sweep[i].back();
				sweep[i].pop_back();
				long long sj = 0LL;
				bool deu = false;
				for(int w = 0 ;  w < own[u].size() ; w++){
					int v = own[u][w];
					sj += query(v);
					if(sj >= qt[u]){
						deu = true;
						break;
					}
				}
				if(deu){
					if(l[u] == r[u]) ans[u] = i , r[u] = -1;
					else r[u] = i;
				}
				else{
					if(l[u] == r[u]) r[u] = -1;
					else l[u] = i + 1;
				}
			}
		}
	}
	for(int i = 1 ; i <= n; i++){
		if(ans[i] == -1) puts("NIE");
		else printf("%d\n" , ans[i] );
	}

}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int w = 0 ;  w < own[u].size() ; w++){
                        ^
met.cpp:48:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &m);
                         ^
met.cpp:51:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
                   ^
met.cpp:54:53: 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("%lld" , &qt[i]);
                                                     ^
met.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &k);
                  ^
met.cpp:57:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &querys[i].F.F , &querys[i].F.S , &querys[i].S);
                                                                   ^

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13