oj.uz

답안 #131477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131477 2019-07-17T07:46:23 Z SirCeness Examination (JOI19_examination) C++14
20 / 100
 1055 ms 63304 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;
		}
		
		if (st[l].first < a) cout << 0 << endl;
		else 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 30 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1055 ms 62516 KB Output is correct
2 Correct 925 ms 62832 KB Output is correct
3 Correct 914 ms 62724 KB Output is correct
4 Correct 844 ms 52076 KB Output is correct
5 Correct 892 ms 62908 KB Output is correct
6 Correct 519 ms 51736 KB Output is correct
7 Correct 851 ms 62616 KB Output is correct
8 Correct 828 ms 62704 KB Output is correct
9 Correct 752 ms 62580 KB Output is correct
10 Correct 674 ms 62264 KB Output is correct
11 Correct 698 ms 51768 KB Output is correct
12 Correct 477 ms 51768 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1055 ms 62516 KB Output is correct
2 Correct 925 ms 62832 KB Output is correct
3 Correct 914 ms 62724 KB Output is correct
4 Correct 844 ms 52076 KB Output is correct
5 Correct 892 ms 62908 KB Output is correct
6 Correct 519 ms 51736 KB Output is correct
7 Correct 851 ms 62616 KB Output is correct
8 Correct 828 ms 62704 KB Output is correct
9 Correct 752 ms 62580 KB Output is correct
10 Correct 674 ms 62264 KB Output is correct
11 Correct 698 ms 51768 KB Output is correct
12 Correct 477 ms 51768 KB Output is correct
13 Incorrect 945 ms 63304 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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