oj.uz

Submission #41240

# Submission time Handle Problem Language Result Execution time Memory
41240 2018-02-15T05:06:38 Z wzy Meteors (POI11_met) C++11
24 / 100
 6000 ms 23348 KB 
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

inline int read_int() {
   register char c=0;
   int a=0;
   while (c<33) c=getchar();
   while (c>33) {
       a=a*10+c-'0', c=getchar();
   }
   return a;
}


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;
	}
}

long long qr(int x){
	if(x == 0) return 0;
	long long 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);
}

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


void solve(int l , int r ,  const 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); 
	}
	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(){
	n = read_int() , m = read_int();
	vector<int> candidatos;
	for(int i = 1 ; i <= m;i++){
		int x;
		x = read_int();
		o[x].push_back(i);
	}
	for(int i = 1 ; i<= n ;i++){
		qt[i] = read_int();
		candidatos.push_back(i);
	}
	k = read_int();
	for(int i = 0 ; i < k ;i ++){
		int l , r ,v;
		l = read_int() , r = read_int() , v =read_int();
		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, const std::vector<int>&)':
met.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0 ; j < opt.size() ; j++){
                    ^
met.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int w = 0 ; w < o[i].size(); w++){
                     ^
met.cpp:82: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:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < rightc.size();i++) ans[rightc[i]] = -1;
                     ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9720 KB Output is correct
2 Correct 36 ms 9824 KB Output is correct
3 Correct 172 ms 9876 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9948 KB Output is correct
2 Correct 15 ms 9948 KB Output is correct
3 Correct 247 ms 10000 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 11344 KB Output is correct
2 Correct 3546 ms 13340 KB Output is correct
3 Execution timed out 6065 ms 13340 KB Time limit exceeded

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6039 ms 13340 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 6034 ms 13340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2631 ms 13340 KB Output is correct
2 Execution timed out 6068 ms 13340 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 6047 ms 23348 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 6060 ms 23348 KB Time limit exceeded
2 Halted 0 ms 0 KB -