oj.uz

답안 #260031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260031 2020-08-09T03:41:06 Z minhcool Examination (JOI19_examination) C++17
22 / 100
 116 ms 9336 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define er erase

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int oo = 1e18 + 7, mod = 1e9 + 7;

const int N = 1e5 + 5;

int n, q, BIT[N], ans[N];
iii queries[N];
ii students[N];

void update(int u){
	for(; u <= 100001 && u; u += (u & -u)){
		//cout << u << " " << u + (u & -u) << "\n";
		++BIT[u];
	}
}

int get(int u){
	if(u < 0) return 0;
	int sum = 0;
	for(; u; u -= (u & -u)) sum += BIT[u];
	return sum;
}

bool cmp(iii a, iii b){
	if(a.fi != b.fi) return a.fi > b.fi;
	return 0;
}

signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("examination_19.inp", "r", stdin);
	//freopen("examination_19.out", "w", stdout);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> students[i].fi >> students[i].se;
		++students[i].fi;
		++students[i].se;
	}
	sort(students + 1, students + n + 1, greater<ii>());
	if(n <= 3000 && q <= 3000){
		while(q--){
			int x, y, z, ans = 0;
			cin >> x >> y >> z;
			++x;
			++y;
			z += 2;
			for(int i = 1; i <= n; i++) ans += (x <= students[i].fi && y <= students[i].se && z <= (students[i].fi + students[i].se));
			cout << ans << "\n";
		}
	}
	else{
		for(int i = 1; i <= q; i++){
			//cout << i << "\n";
			int z;
			cin >> queries[i].fi.fi >> queries[i].fi.se >> z;
			++queries[i].fi.fi;
			++queries[i].fi.se;
			queries[i].se = i;
		}
		sort(queries + 1, queries + q + 1, cmp);
		int itr = 1;
		for(int i = 1; i <= q; i++){
			//cout << i << "\n";
			while(itr <= n && students[itr].fi >= queries[i].fi.fi){
				update(students[itr].se);
				++itr;
				//cout << itr << "\n";
			}
			ans[queries[i].se] = itr - 1 - get(queries[i].fi.se - 1);
		}
		for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
	}
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 29 ms 384 KB Output is correct
8 Correct 30 ms 384 KB Output is correct
9 Correct 29 ms 384 KB Output is correct
10 Correct 29 ms 384 KB Output is correct
11 Correct 19 ms 384 KB Output is correct
12 Correct 19 ms 384 KB Output is correct
13 Correct 29 ms 504 KB Output is correct
14 Correct 30 ms 384 KB Output is correct
15 Correct 30 ms 384 KB Output is correct
16 Correct 19 ms 384 KB Output is correct
17 Correct 19 ms 384 KB Output is correct
18 Correct 29 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 6520 KB Output is correct
2 Correct 103 ms 8840 KB Output is correct
3 Correct 101 ms 8828 KB Output is correct
4 Correct 95 ms 7416 KB Output is correct
5 Correct 100 ms 8184 KB Output is correct
6 Correct 82 ms 6648 KB Output is correct
7 Correct 105 ms 8824 KB Output is correct
8 Correct 102 ms 8824 KB Output is correct
9 Correct 99 ms 8696 KB Output is correct
10 Correct 90 ms 7928 KB Output is correct
11 Correct 91 ms 7160 KB Output is correct
12 Correct 64 ms 6264 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 6520 KB Output is correct
2 Correct 103 ms 8840 KB Output is correct
3 Correct 101 ms 8828 KB Output is correct
4 Correct 95 ms 7416 KB Output is correct
5 Correct 100 ms 8184 KB Output is correct
6 Correct 82 ms 6648 KB Output is correct
7 Correct 105 ms 8824 KB Output is correct
8 Correct 102 ms 8824 KB Output is correct
9 Correct 99 ms 8696 KB Output is correct
10 Correct 90 ms 7928 KB Output is correct
11 Correct 91 ms 7160 KB Output is correct
12 Correct 64 ms 6264 KB Output is correct
13 Incorrect 113 ms 9336 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 288 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 29 ms 384 KB Output is correct
8 Correct 30 ms 384 KB Output is correct
9 Correct 29 ms 384 KB Output is correct
10 Correct 29 ms 384 KB Output is correct
11 Correct 19 ms 384 KB Output is correct
12 Correct 19 ms 384 KB Output is correct
13 Correct 29 ms 504 KB Output is correct
14 Correct 30 ms 384 KB Output is correct
15 Correct 30 ms 384 KB Output is correct
16 Correct 19 ms 384 KB Output is correct
17 Correct 19 ms 384 KB Output is correct
18 Correct 29 ms 384 KB Output is correct
19 Correct 116 ms 6520 KB Output is correct
20 Correct 103 ms 8840 KB Output is correct
21 Correct 101 ms 8828 KB Output is correct
22 Correct 95 ms 7416 KB Output is correct
23 Correct 100 ms 8184 KB Output is correct
24 Correct 82 ms 6648 KB Output is correct
25 Correct 105 ms 8824 KB Output is correct
26 Correct 102 ms 8824 KB Output is correct
27 Correct 99 ms 8696 KB Output is correct
28 Correct 90 ms 7928 KB Output is correct
29 Correct 91 ms 7160 KB Output is correct
30 Correct 64 ms 6264 KB Output is correct
31 Incorrect 113 ms 9336 KB Output isn't correct
32 Halted 0 ms 0 KB -