제출 #41237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41237		wzy	새로운 문제 (POI11_met)	C++14	24 / 100	6058 ms	44352 KiB

met

#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]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13