oj.uz

Submission #131477

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -