oj.uz

답안 #629998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629998 2022-08-15T13:43:28 Z Arnch Examination (JOI19_examination) C++17
100 / 100
 1257 ms 140116 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 5e5 + 10, MOD = 1e9 + 7, SQ = 700;

int n, q; 
int x[N], y[N], sum[N];
int a[N], b[N], c[N];
int fen[N / SQ][N], cur[N];
int id[N], last[N];
int ans_t[N];

void compress() {
	vector<int> vc;
	for(int i = 0; i < n; i++) {
		vc.push_back(x[i]), vc.push_back(x[i] + y[i]);
	}
	for(int i = 0; i < q; i++) {
		vc.push_back(a[i]), vc.push_back(c[i]);
	}
	sort(All(vc));
	for(int i = 0; i < n; i++) {
		sum[i] = lower_bound(All(vc), x[i] + y[i]) - vc.begin();
		x[i] = lower_bound(All(vc), x[i]) - vc.begin();
	}	
	for(int i = 0; i < q; i++) {
		a[i] = lower_bound(All(vc), a[i]) - vc.begin();
		c[i] = lower_bound(All(vc), c[i]) - vc.begin();
	}

	vector<pair<int, int> > block, b2;
	for(int i = 0; i < n; i++) block.push_back({x[i], i});
	for(int i = 0; i < q; i++) b2.push_back({a[i], i});
	sort(All(block)), sort(All(b2));

	for(int i = n - 1; i >= 0; i--) {
		id[block[i].second] = i;
		while(!b2.empty() && b2.back().first > block[i].first) {
			last[b2.back().first] = i + 1;
			b2.pop_back();
		}
	}
	while(!b2.empty()) {
		last[b2.back().first] = 0;
		b2.pop_back();
	}
}
bool cmp(pair<int, int> i, pair<int, int> j) {
	int cnt1 = 0, cnt2 = 0;
	if(i.second == 0) cnt1 = y[i.first];
	else cnt1 = b[i.first];

	if(j.second == 0) cnt2 = y[j.first];
	else cnt2 = b[j.first];

	if(cnt1 != cnt2) return cnt1 > cnt2;
	return i.second < j.second;
}

void add_fen(int ind, int pos) {
	for(++pos; pos; pos -= (pos & -pos)) 
		fen[ind][pos]++;
}
int get_fen(int ind, int pos) {
	int ans = 0;
	for(++pos; pos < N; pos += (pos & -pos)) 
		ans += fen[ind][pos];
	return ans;
}

void add(int pos, int val) {
	cur[pos] = val;
	add_fen(pos / SQ, val);
}
int solve(int pos, int val) {
	int ans = 0;
	for(int i = pos; i / SQ == pos / SQ; i++) {
		if(cur[i] >= val) ans++;
	}	
	for(int i = pos / SQ + 1; i <= (n - 1) / SQ; i++) {
		ans += get_fen(i, val);
	}
	return ans;
}

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);

	cin >>n >>q;
	for(int i = 0; i < n; i++) cin >>x[i] >>y[i];
	for(int i = 0; i < q; i++) cin >>a[i] >>b[i] >>c[i];

	compress();

	vector<pair<int, int> > pos;
	for(int i = 0; i < n; i++) {
		pos.push_back(mak(i, 0));
	}
	for(int i = 0; i < q; i++) {
		pos.push_back(mak(i, 1));
	}
	sort(All(pos), cmp);

	memset(cur, -1, sizeof(cur));
	for(auto j : pos) {
		//cout<<j.first <<' ' <<j.second <<' ';
		//if(j.second == 0) cout<<sum[j.first] <<endl;
		//else cout<<c[j.first] <<endl;

		/*if(j.second == 0) {
			cout<<"^^" <<j.first <<' ' <<id[j.first] <<' ' <<sum[j.first] <<endl;
		} else {
			cout<<"***" <<j.first <<' ' <<last[a[j.first]] <<' ' <<c[j.first] <<endl;
		}*/
	
		if(j.second == 0) {
			add(id[j.first], sum[j.first]);
			continue;
		}
		ans_t[j.first] = solve(last[a[j.first]], c[j.first]);
	}

	for(int j = 0; j < q; j++)
		cout<<ans_t[j] <<endl;

	return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 13 ms 2776 KB Output is correct
8 Correct 12 ms 2748 KB Output is correct
9 Correct 12 ms 2712 KB Output is correct
10 Correct 11 ms 2620 KB Output is correct
11 Correct 11 ms 2736 KB Output is correct
12 Correct 12 ms 2748 KB Output is correct
13 Correct 15 ms 2788 KB Output is correct
14 Correct 11 ms 2712 KB Output is correct
15 Correct 11 ms 2684 KB Output is correct
16 Correct 10 ms 2696 KB Output is correct
17 Correct 10 ms 2732 KB Output is correct
18 Correct 8 ms 2620 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 761 ms 106004 KB Output is correct
2 Correct 774 ms 108304 KB Output is correct
3 Correct 763 ms 108616 KB Output is correct
4 Correct 674 ms 17240 KB Output is correct
5 Correct 701 ms 70152 KB Output is correct
6 Correct 583 ms 34292 KB Output is correct
7 Correct 1067 ms 83116 KB Output is correct
8 Correct 671 ms 108384 KB Output is correct
9 Correct 1004 ms 82852 KB Output is correct
10 Correct 844 ms 69864 KB Output is correct
11 Correct 561 ms 16888 KB Output is correct
12 Correct 409 ms 11392 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 761 ms 106004 KB Output is correct
2 Correct 774 ms 108304 KB Output is correct
3 Correct 763 ms 108616 KB Output is correct
4 Correct 674 ms 17240 KB Output is correct
5 Correct 701 ms 70152 KB Output is correct
6 Correct 583 ms 34292 KB Output is correct
7 Correct 1067 ms 83116 KB Output is correct
8 Correct 671 ms 108384 KB Output is correct
9 Correct 1004 ms 82852 KB Output is correct
10 Correct 844 ms 69864 KB Output is correct
11 Correct 561 ms 16888 KB Output is correct
12 Correct 409 ms 11392 KB Output is correct
13 Correct 905 ms 135600 KB Output is correct
14 Correct 877 ms 134448 KB Output is correct
15 Correct 751 ms 108440 KB Output is correct
16 Correct 690 ms 18068 KB Output is correct
17 Correct 829 ms 126044 KB Output is correct
18 Correct 614 ms 32596 KB Output is correct
19 Correct 965 ms 135672 KB Output is correct
20 Correct 884 ms 140116 KB Output is correct
21 Correct 1073 ms 122088 KB Output is correct
22 Correct 705 ms 69932 KB Output is correct
23 Correct 570 ms 16932 KB Output is correct
24 Correct 393 ms 11424 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 13 ms 2776 KB Output is correct
8 Correct 12 ms 2748 KB Output is correct
9 Correct 12 ms 2712 KB Output is correct
10 Correct 11 ms 2620 KB Output is correct
11 Correct 11 ms 2736 KB Output is correct
12 Correct 12 ms 2748 KB Output is correct
13 Correct 15 ms 2788 KB Output is correct
14 Correct 11 ms 2712 KB Output is correct
15 Correct 11 ms 2684 KB Output is correct
16 Correct 10 ms 2696 KB Output is correct
17 Correct 10 ms 2732 KB Output is correct
18 Correct 8 ms 2620 KB Output is correct
19 Correct 761 ms 106004 KB Output is correct
20 Correct 774 ms 108304 KB Output is correct
21 Correct 763 ms 108616 KB Output is correct
22 Correct 674 ms 17240 KB Output is correct
23 Correct 701 ms 70152 KB Output is correct
24 Correct 583 ms 34292 KB Output is correct
25 Correct 1067 ms 83116 KB Output is correct
26 Correct 671 ms 108384 KB Output is correct
27 Correct 1004 ms 82852 KB Output is correct
28 Correct 844 ms 69864 KB Output is correct
29 Correct 561 ms 16888 KB Output is correct
30 Correct 409 ms 11392 KB Output is correct
31 Correct 905 ms 135600 KB Output is correct
32 Correct 877 ms 134448 KB Output is correct
33 Correct 751 ms 108440 KB Output is correct
34 Correct 690 ms 18068 KB Output is correct
35 Correct 829 ms 126044 KB Output is correct
36 Correct 614 ms 32596 KB Output is correct
37 Correct 965 ms 135672 KB Output is correct
38 Correct 884 ms 140116 KB Output is correct
39 Correct 1073 ms 122088 KB Output is correct
40 Correct 705 ms 69932 KB Output is correct
41 Correct 570 ms 16932 KB Output is correct
42 Correct 393 ms 11424 KB Output is correct
43 Correct 889 ms 137756 KB Output is correct
44 Correct 892 ms 137652 KB Output is correct
45 Correct 877 ms 136140 KB Output is correct
46 Correct 678 ms 19320 KB Output is correct
47 Correct 894 ms 126948 KB Output is correct
48 Correct 573 ms 31996 KB Output is correct
49 Correct 1213 ms 111816 KB Output is correct
50 Correct 857 ms 137316 KB Output is correct
51 Correct 1257 ms 111916 KB Output is correct
52 Correct 892 ms 126756 KB Output is correct
53 Correct 561 ms 17860 KB Output is correct