제출 #105562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105562		Pro_ktmr	Examination (JOI19_examination)	C++14	100 / 100	1489 ms	82472 KiB

examination

#include"bits/stdc++.h"
using namespace std;
#define MP make_pair
#define PB push_back

int N,Q;
vector<pair<int,int>> score;//math,info
vector<pair<int,int>> score2;//info,moto
vector<pair<pair<int,int>,pair<int,int>>> query;//info,math,sum,moto
int ans[100000];

struct RSQ{
public:
	int N;
	vector<int> sorted;
	vector<bool> already;
	vector<int> node;
	
	void init(int n){
		N = n;
		for(int i=0; i<2*N-1; i++) node.PB(0);
	}
	void add(int x){
		int k = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
		k += N-1;
		node[k]++;
		while(k > 0){
			k = (k-1)/2;
			node[k]++;
		}
	}
	int sum(int x){
		x = lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin();
		return query(x, N, 0, 0, N);
	}
	int query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l) return 0;
		if(a <= l && r <= b){
			return node[k];
		}
		return query(a, b, 2*k+1, l, (l+r)/2) + query(a, b, 2*k+2, (l+r)/2, r);
	}
};

struct SegmentTree{
public:
	int N;
	RSQ node[100000*4];
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		rsq(0, 0, N, n);
	}
	void rsq(int k, int l, int r, int n){
		node[k].init(r-l);
		for(int i=l; i<min(r,n); i++){
			node[k].sorted.PB(score[i].first+score[i].second);
		}
		/*for(int i=min(r,n); i<r; i++){
			node[k].sorted.PB(-1);
			already
		}*/
		sort(node[k].sorted.begin(), node[k].sorted.end());
		if(r-l != 1){
			rsq(2*k+1, l, (l+r)/2, n);
			rsq(2*k+2, (l+r)/2, r, n);
		}
	}
	void add(int k){
		int i = k;
		k += N-1;
		node[k].add(score[i].first+score[i].second);
		while(k > 0){
			k = (k-1)/2;
			node[k].add(score[i].first+score[i].second);
		}
	}
	int culc(int a, int b, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = N;
		if(r <= a || b <= l) return 0;
		if(a <= l && r <= b){
			return node[k].sum(x);
		}
		else{
			return culc(a, b, x, 2*k+1, l, (l+r)/2) + culc(a, b, x, 2*k+2, (l+r)/2, r);
		}
	}
};

SegmentTree st;
signed main(){
	scanf("%d%d", &N, &Q);
	score.resize(N);
	for(int i=0; i<N; i++){
		scanf("%d%d", &score[i].first, &score[i].second);
	}
	sort(score.begin(), score.end());
	query.resize(Q);
	for(int i=0; i<Q; i++){
		scanf("%d%d%d", &query[i].first.second, &query[i].first.first, &query[i].second.first);
		query[i].second.second = i;
	}
	sort(query.begin(), query.end());
	
	for(int i=0; i<N; i++) score2.PB(MP(score[i].second, i));
	sort(score2.begin(), score2.end());
	
	//
	
	st.init(N);
	
	int now = N-1;
	for(int i=Q-1; i>=0; i--){
		while(now >=0 && score2[now].first >= query[i].first.first){
			st.add(score2[now].second);
			now--;
		}
		int a = lower_bound(score.begin(), score.end(), MP(query[i].first.second, 0)) - score.begin();
		ans[query[i].second.second] = st.culc(a, N, query[i].second.first);
	}
	
	for(int i=0; i<Q; i++){
		printf("%d\n", ans[i]);
	}
	
	return 0;
}

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

examination.cpp: In function 'int main()':
examination.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &score[i].first, &score[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &query[i].first.second, &query[i].first.first, &query[i].second.first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57