oj.uz

답안 #106731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106731 2019-04-19T22:05:22 Z eriksuenderhauf Examination (JOI19_examination) C++11
100 / 100
 2286 ms 385712 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 7;
const int MAXN = 4e5 + 5;
const double eps = 1e-9;
pii a[MAXN];

struct nodeX {
	vector<vi> seg;
	vi arr, sm;
} seg[MAXN];

void build(int l, int r, int k, int k2, vi &sm) {
	if (l == r) {
		seg[k2].seg[k] = {sm[l]};
		return;
	}
	int m = (l + r) / 2;
	build(l, m, k*2, k2, sm);
	build(m+1, r, k*2+1, k2, sm);
	int i = 0, j = 0;
	while (i < (int)seg[k2].seg[k*2].size() && j < (int)seg[k2].seg[k*2+1].size())
		if (seg[k2].seg[k*2][i] < seg[k2].seg[k*2+1][j])
			seg[k2].seg[k].pb(seg[k2].seg[k*2][i++]);
		else
			seg[k2].seg[k].pb(seg[k2].seg[k*2+1][j++]);
	while (i < (int)seg[k2].seg[k*2].size())
		seg[k2].seg[k].pb(seg[k2].seg[k*2][i++]);
	while (j < (int)seg[k2].seg[k*2+1].size())
		seg[k2].seg[k].pb(seg[k2].seg[k*2+1][j++]);
}

void build(int l, int r, int k) {
	if (l == r) {
		seg[k].arr = {a[l].se};
		seg[k].sm = {a[l].fi + a[l].se};
		seg[k].seg.resize(2);
		build(0, 0, 1, k, seg[k].sm);
		return;
	}
	seg[k].seg.resize(4*(r-l+1)+1);
	int m = (l + r) / 2;
	build(l, m, k * 2);
	build(m + 1, r, k * 2 + 1);
	int i = 0, j = 0;
	while (i < (int)seg[k*2].arr.size() && j < (int)seg[k*2+1].arr.size()) {
		if (seg[k*2].arr[i] < seg[k*2+1].arr[j]) {
			seg[k].arr.pb(seg[k*2].arr[i]);
			seg[k].sm.pb(seg[k*2].sm[i++]);
		} else {
			seg[k].arr.pb(seg[k*2+1].arr[j]);
			seg[k].sm.pb(seg[k*2+1].sm[j++]);
		}
	}
	while (i < (int)seg[k*2].arr.size()) {
		seg[k].arr.pb(seg[k*2].arr[i]);
		seg[k].sm.pb(seg[k*2].sm[i++]);
	}
	while (j < (int)seg[k*2+1].arr.size()) {
		seg[k].arr.pb(seg[k*2+1].arr[j]);
		seg[k].sm.pb(seg[k*2+1].sm[j++]);
	}
	build(0, r - l, 1, k, seg[k].sm);
}

int qry1(int l, int r, int k, int k2, int a, int b, int z) {
	if (r < a || b < l) return 0;
	if (a <= l && r <= b) {
		/*cout << "print seg2:" << l << " " << r << "\n";
		for (int i: seg[k2].seg[k])
			cout << i << " ";
		cout << "\n";*/
		int lo = lower_bound(seg[k2].seg[k].begin(), seg[k2].seg[k].end(), z) - seg[k2].seg[k].begin();
		//cout << lo << " " << " ret " << (int)seg[k2].seg[k].size() - lo + 1 << "\n";
		return (int)seg[k2].seg[k].size() - lo;
	}
	int m = (l + r) / 2;
	return qry1(l, m, k*2, k2, a, b, z) + qry1(m+1, r, k*2+1, k2, a, b, z);
}

int qry(int l, int r, int k, int a, int b, int y, int z) {
	if (r < a || b < l) return 0;
	if (a <= l && r <= b) {
		/*cout << "print:" << l << " " << r << "\n";
		for (int i: seg[k].arr)
			cout << i << " ";
		cout << "\n";
		for (int i: seg[k].sm)
			cout << i << " ";
		cout << "\n";*/
		int lo = lower_bound(seg[k].arr.begin(), seg[k].arr.end(), y) - seg[k].arr.begin();
		//cout << lo << "\n";
		return qry1(0, r - l, 1, k, lo, r - l, z);
	}
	int m = (l + r) / 2;
	return qry(l, m, k*2, a, b, y, z) + qry(m + 1, r, k*2+1, a, b, y, z);
}

int main() {
	int n, q;
	scanf("%d %d", &n, &q);
	for (int i = 0; i < n; i++)
		scanf("%d %d", &a[i].fi, &a[i].se);
	sort(a, a + n);
	/*for (int i = 0; i < n; i++)
		cout << a[i].fi << " : " << a[i].se << "\n";*/
	build(0, n - 1, 1);
	for (int i = 0; i < q; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		int lo = lower_bound(a, a + n, mp(x, -1)) - a;
		//cout << lo << "\n";
		pri(qry(0, n - 1, 1, lo, n - 1, y, z));
	}
    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i].fi, &a[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28560 KB Output is correct
2 Correct 32 ms 28492 KB Output is correct
3 Correct 29 ms 28556 KB Output is correct
4 Correct 29 ms 28448 KB Output is correct
5 Correct 28 ms 28556 KB Output is correct
6 Correct 28 ms 28544 KB Output is correct
7 Correct 62 ms 35960 KB Output is correct
8 Correct 55 ms 35808 KB Output is correct
9 Correct 58 ms 35832 KB Output is correct
10 Correct 57 ms 35728 KB Output is correct
11 Correct 56 ms 35808 KB Output is correct
12 Correct 56 ms 35704 KB Output is correct
13 Correct 76 ms 35832 KB Output is correct
14 Correct 72 ms 35832 KB Output is correct
15 Correct 71 ms 35988 KB Output is correct
16 Correct 51 ms 35796 KB Output is correct
17 Correct 51 ms 35832 KB Output is correct
18 Correct 47 ms 35704 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2072 ms 383316 KB Output is correct
2 Correct 1966 ms 383356 KB Output is correct
3 Correct 2029 ms 383268 KB Output is correct
4 Correct 1742 ms 382516 KB Output is correct
5 Correct 1380 ms 382392 KB Output is correct
6 Correct 1143 ms 381780 KB Output is correct
7 Correct 1813 ms 383192 KB Output is correct
8 Correct 1667 ms 383180 KB Output is correct
9 Correct 1542 ms 383156 KB Output is correct
10 Correct 1114 ms 382396 KB Output is correct
11 Correct 1205 ms 382312 KB Output is correct
12 Correct 1027 ms 381388 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2072 ms 383316 KB Output is correct
2 Correct 1966 ms 383356 KB Output is correct
3 Correct 2029 ms 383268 KB Output is correct
4 Correct 1742 ms 382516 KB Output is correct
5 Correct 1380 ms 382392 KB Output is correct
6 Correct 1143 ms 381780 KB Output is correct
7 Correct 1813 ms 383192 KB Output is correct
8 Correct 1667 ms 383180 KB Output is correct
9 Correct 1542 ms 383156 KB Output is correct
10 Correct 1114 ms 382396 KB Output is correct
11 Correct 1205 ms 382312 KB Output is correct
12 Correct 1027 ms 381388 KB Output is correct
13 Correct 2081 ms 383828 KB Output is correct
14 Correct 1956 ms 383824 KB Output is correct
15 Correct 1899 ms 383292 KB Output is correct
16 Correct 1981 ms 382848 KB Output is correct
17 Correct 1310 ms 382860 KB Output is correct
18 Correct 1186 ms 381808 KB Output is correct
19 Correct 2286 ms 383860 KB Output is correct
20 Correct 2120 ms 383644 KB Output is correct
21 Correct 1982 ms 383812 KB Output is correct
22 Correct 1105 ms 382376 KB Output is correct
23 Correct 1210 ms 382280 KB Output is correct
24 Correct 1050 ms 381432 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28560 KB Output is correct
2 Correct 32 ms 28492 KB Output is correct
3 Correct 29 ms 28556 KB Output is correct
4 Correct 29 ms 28448 KB Output is correct
5 Correct 28 ms 28556 KB Output is correct
6 Correct 28 ms 28544 KB Output is correct
7 Correct 62 ms 35960 KB Output is correct
8 Correct 55 ms 35808 KB Output is correct
9 Correct 58 ms 35832 KB Output is correct
10 Correct 57 ms 35728 KB Output is correct
11 Correct 56 ms 35808 KB Output is correct
12 Correct 56 ms 35704 KB Output is correct
13 Correct 76 ms 35832 KB Output is correct
14 Correct 72 ms 35832 KB Output is correct
15 Correct 71 ms 35988 KB Output is correct
16 Correct 51 ms 35796 KB Output is correct
17 Correct 51 ms 35832 KB Output is correct
18 Correct 47 ms 35704 KB Output is correct
19 Correct 2072 ms 383316 KB Output is correct
20 Correct 1966 ms 383356 KB Output is correct
21 Correct 2029 ms 383268 KB Output is correct
22 Correct 1742 ms 382516 KB Output is correct
23 Correct 1380 ms 382392 KB Output is correct
24 Correct 1143 ms 381780 KB Output is correct
25 Correct 1813 ms 383192 KB Output is correct
26 Correct 1667 ms 383180 KB Output is correct
27 Correct 1542 ms 383156 KB Output is correct
28 Correct 1114 ms 382396 KB Output is correct
29 Correct 1205 ms 382312 KB Output is correct
30 Correct 1027 ms 381388 KB Output is correct
31 Correct 2081 ms 383828 KB Output is correct
32 Correct 1956 ms 383824 KB Output is correct
33 Correct 1899 ms 383292 KB Output is correct
34 Correct 1981 ms 382848 KB Output is correct
35 Correct 1310 ms 382860 KB Output is correct
36 Correct 1186 ms 381808 KB Output is correct
37 Correct 2286 ms 383860 KB Output is correct
38 Correct 2120 ms 383644 KB Output is correct
39 Correct 1982 ms 383812 KB Output is correct
40 Correct 1105 ms 382376 KB Output is correct
41 Correct 1210 ms 382280 KB Output is correct
42 Correct 1050 ms 381432 KB Output is correct
43 Correct 2090 ms 385664 KB Output is correct
44 Correct 1829 ms 385632 KB Output is correct
45 Correct 1834 ms 385568 KB Output is correct
46 Correct 1681 ms 383988 KB Output is correct
47 Correct 1446 ms 384104 KB Output is correct
48 Correct 1270 ms 381644 KB Output is correct
49 Correct 2015 ms 385712 KB Output is correct
50 Correct 2115 ms 385700 KB Output is correct
51 Correct 1779 ms 385540 KB Output is correct
52 Correct 1222 ms 383920 KB Output is correct
53 Correct 1357 ms 383224 KB Output is correct