제출 #131477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131477		SirCeness	Examination (JOI19_examination)	C++14	20 / 100	1055 ms	63304 KiB

examination

#include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

int n, q;
pair<ll, ll> st[100005];

struct node {
	vector<int> arr;
	vector<int> mapl;
	vector<int> mapr;
};

node wt[4*100005];

void wtc(int nod, int l, int r){
	if (l == r) return;
	int m = (l+r)/2;
	int ansl = -1;
	int ansr = -1;
	for (int i = 0; i < wt[nod].arr.size(); i++){
		if (wt[nod].arr[i] <= m){
			ansl++;
			wt[nod*2].arr.pb(wt[nod].arr[i]);
		} else {
			ansr++;
			wt[nod*2+1].arr.pb(wt[nod].arr[i]);
		}
		wt[nod].mapl.pb(ansl);
		wt[nod].mapr.pb(ansr);
	}
	wtc(nod*2, l, m);
	wtc(nod*2+1, m+1, r);
}

int mapl(int nod, int a){
	if (a == -1) return -1;
	else return wt[nod].mapl[a];
}

int mapr(int nod, int a){
	if (a == -1) return -1;
	else return wt[nod].mapr[a];
}

int wtq(int nod, int l, int r, int sl, int sr, int rl, int rr){
	if (inside) return rr-rl+1;
	else if (outside) return 0;
	else {
		int m = (l+r)/2;
		return 
			wtq(nod*2, l, m, sl, sr, mapl(nod, rl-1)+1, mapl(nod, rr)) + 
			wtq(nod*2+1, m+1, r, sl, sr, mapr(nod, rl-1)+1, mapr(nod, rr)); 
	}
}

int main(){
	cin >> n >> q;
	for (int i = 0; i < n; i++){
		cin >> st[i].first >> st[i].second;
	}
	
	sort(st, st+n);
	
	for (int i = 0; i < n; i++){
		wt[1].arr.pb(st[i].second);
	}
	
	wtc(1, 0, 100000);
	
	for (int i = 0; i < q; i++){
		int a, b, c;
		cin >> a >> b >> c;
		
		int l = 0;
		int r = n-1;
		while (l < r){
			int m = (l+r)/2;
			if (st[m].first < a) l = m+1;
			else r = m;
		}
		
		if (st[l].first < a) cout << 0 << endl;
		else cout << wtq(1, 0, 100000, b, 100000, l, n-1) << endl;
	}
	
}

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

examination.cpp: In function 'void wtc(int, int, int)':
examination.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < wt[nod].arr.size(); i++){
                  ~~^~~~~~~~~~~~~~~~~~~~

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