oj.uz

Submission #41305

# Submission time Handle Problem Language Result Execution time Memory
41305 2018-02-15T20:57:52 Z wzy Meteors (POI11_met) C++11
74 / 100
 1654 ms 35008 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14560 KB Output is correct
3 Correct 16 ms 14632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14704 KB Output is correct
2 Correct 15 ms 14704 KB Output is correct
3 Correct 16 ms 14780 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 16440 KB Output is correct
2 Correct 222 ms 18744 KB Output is correct
3 Correct 163 ms 18744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 18744 KB Output is correct
2 Correct 179 ms 18744 KB Output is correct
3 Correct 228 ms 18764 KB Output is correct
4 Correct 52 ms 18764 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 18764 KB Output is correct
2 Correct 232 ms 19360 KB Output is correct
3 Correct 166 ms 19360 KB Output is correct
4 Correct 167 ms 19360 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 19360 KB Output is correct
2 Correct 200 ms 19360 KB Output is correct
3 Correct 131 ms 19360 KB Output is correct
4 Correct 228 ms 20184 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1539 ms 35008 KB Output is correct
2 Incorrect 909 ms 35008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1654 ms 35008 KB Output is correct
2 Incorrect 955 ms 35008 KB Output isn't correct
3 Halted 0 ms 0 KB -