oj.uz

답안 #131475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131475 2019-07-17T07:41:12 Z SirCeness Examination (JOI19_examination) C++14
0 / 100
 978 ms 63576 KB 
#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;
		}
		
		cout << wtq(1, 0, 100000, b, 100000, l, n-1) << endl;
	}
	
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 978 ms 63488 KB Output is correct
2 Correct 959 ms 63388 KB Output is correct
3 Correct 941 ms 63332 KB Output is correct
4 Correct 802 ms 52560 KB Output is correct
5 Correct 792 ms 63576 KB Output is correct
6 Correct 522 ms 52492 KB Output is correct
7 Correct 834 ms 63296 KB Output is correct
8 Correct 858 ms 63348 KB Output is correct
9 Correct 771 ms 63316 KB Output is correct
10 Incorrect 744 ms 63116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 978 ms 63488 KB Output is correct
2 Correct 959 ms 63388 KB Output is correct
3 Correct 941 ms 63332 KB Output is correct
4 Correct 802 ms 52560 KB Output is correct
5 Correct 792 ms 63576 KB Output is correct
6 Correct 522 ms 52492 KB Output is correct
7 Correct 834 ms 63296 KB Output is correct
8 Correct 858 ms 63348 KB Output is correct
9 Correct 771 ms 63316 KB Output is correct
10 Incorrect 744 ms 63116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -