Submission #41237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41237	2018-02-15T04:59:36 Z	wzy	Meteors (POI11_met)	C++14	24 / 100	6000 ms	44352 KB

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int ans[300005],n , m  , qt[300005] , k;
vector<int> o[300005];
vector<pair< pair<int,int> , int > > querys;

long long bit[300005];

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

int qr(int x){
	if(x == 0) return 0;
	int s = 0;
	for(int i = x ; i > 0 ; i-=(i&-i)){
		if(s >= (int) 1e17){
			if(bit[i] >= (int) 1e17) continue;
			else s += bit[i];
		}
		else if(s <= -((int) 1e17)){
			if(bit[i] <= -((int) 1e17)) continue;
			else s+= bit[i];
		}
		else s+= bit[i];
	}
	return s;
}

void update(int x , int y, int vl){
	upd(x, vl);
	upd(y+1, -vl);
}

int query(int x){
	return qr(x);
}


void solve(int l , int r , vector<int> & opt){
	int mid = (l+r)/2;
	memset(bit, 0 , sizeof bit);
	for(int i = 0 ; i < mid ; i++){
		pair< pair<int,int> , int> info = querys[i];
		if(info.F.F > info.F.S){
			update(info.F.F , m  , info.S);
			update(1, info.F.S , info.S);
		}
		else{
			update(info.F.F , info.F.S , info.S);
		}
	}
	vector<int> leftc , rightc;
	for(int j = 0 ; j < opt.size() ; j++){
		int i = opt[j];
		int sj = 0;
		for(int w = 0 ; w < o[i].size(); w++){
			int c = o[i][w];
			sj += query(c);
			if(sj >= qt[i]) break;
		}
		if(sj >= qt[i]) leftc.push_back(i);
		else rightc.push_back(i); 
	}
	opt.clear();
	if(l == r){
		for(int i = 0 ; i < leftc.size();i++) ans[leftc[i]] = l;
		for(int i = 0 ; i < rightc.size();i++) ans[rightc[i]] = -1;
		leftc.clear() , rightc.clear();
		return;
	}
	else{
		if(leftc.size()){
			solve(l , mid , leftc);
			leftc.clear();
		}
		if(rightc.size()){
			solve(mid + 1 , r , rightc);
			rightc.clear();
		}
	}
}



int main(){
	scanf("%d%d" , &n , &m);
	vector<int> candidatos;
	for(int i = 1 ; i <= m;i++){
		int x;
		scanf("%d" , &x);
		o[x].push_back(i);
	}
	for(int i = 1 ; i<= n ;i++){
		scanf("%d" , &qt[i]);
		candidatos.push_back(i);
	}
	scanf("%d" , &k);
	for(int i = 0 ; i < k ;i ++){
		int l , r ,v;
		scanf("%d%d%d" , &l , &r , &v);
		querys.push_back(pair<pair<int,int> , int>(pair<int,int>(l , r) , v));
	}
	solve(1, k , candidatos);
	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 'void solve(int, int, std::vector<int>&)':
met.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < opt.size() ; j++){
                    ^
met.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int w = 0 ; w < o[i].size(); w++){
                     ^
met.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < leftc.size();i++) ans[leftc[i]] = l;
                     ^
met.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < rightc.size();i++) ans[rightc[i]] = -1;
                     ^
met.cpp: In function 'int main()':
met.cpp:91: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:95:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
                   ^
met.cpp:99:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &qt[i]);
                       ^
met.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &k);
                  ^
met.cpp:105:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &l , &r , &v);
                                 ^

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	9796 KB	Output is correct
2	Correct	36 ms	9976 KB	Output is correct
3	Correct	158 ms	10116 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	10116 KB	Output is correct
2	Correct	15 ms	10116 KB	Output is correct
3	Correct	241 ms	10296 KB	Output is correct

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	12440 KB	Output is correct
2	Correct	3601 ms	15808 KB	Output is correct
3	Execution timed out	6025 ms	15808 KB	Time limit exceeded

Subtask #4
0 / 12.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2633 ms	17336 KB	Output is correct
2	Execution timed out	6044 ms	18716 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	6046 ms	38756 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	6058 ms	44352 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-