oj.uz

Submission #934382

# Submission time Handle Problem Language Result Execution time Memory
934382 2024-02-27T09:13:27 Z Romicro Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 455 ms 59504 KB 
#include <iostream>
#include <algorithm>
#include <vector>

#define endl '\n'
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define lc (v<<1)
#define rc (v<<1)|1
#define lb(vc, x) lower_bound(vc.begin(), vc.end(), x)
#define ub(vc, x) upper_bound(vc.begin(), vc.end(), x)
#define ll long long

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5+100;

vector<int> seg[1 << 20];
int a[MAXN], b[MAXN];
vector<pii> ques;

int n, sn, k;
ll sm;

int max(int a, int b){
	return (a > b)? a : b;
}

void merge(int v){
	int pl=0, pr=0;

	while(pl < seg[lc].size() and pr < seg[rc].size()){
		if(seg[lc][pl] <= seg[rc][pr]){
			seg[v].pb(seg[lc][pl]);
			pl++;
		}
		else{
			seg[v].pb(seg[rc][pr]);
			pr++;
		}
	}

	while(pl < seg[lc].size()){
		seg[v].pb(seg[lc][pl]);
		pl++;
	}

	while(pr < seg[rc].size()){
		seg[v].pb(seg[rc][pr]);
		pr++;
	}
}

int get_max(int v, int vl, int vr, int l, int r){
	if(vl > r or vr < l) return 0;

	if(l <= vl and vr <= r)
		return seg[v].back();

	int vm = (vl + vr) >> 1;

	int getl = get_max(lc, vl, vm, l, r);
	int getr = get_max(rc, vm+1, vr, l, r);

	return max(getl, getr);
}
	
int cnt_gte(int v, int vl, int vr, int l, int r, int x){
	if(vl > r or vr < l) return 0;

	if(l <= vl and vr <= r)
		return seg[v].end() - lb(seg[v], x);

	int vm = (vl + vr) >> 1;

	int getl = cnt_gte(lc, vl, vm, l, r, x);
	int getr = cnt_gte(rc, vm+1, vr, l, r, x);

	return getl + getr;
}

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

	cin >> n >> k;

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

	for(int i=0; i<k; i++){
		int x;
		cin >> x;
		ques.pb(mp(x, i));
	}

	sort(ques.begin(), ques.end());


	sn = 1;
	while(sn < k) sn <<= 1;

	for(int i=0; i<k; i++)
		seg[i + sn].pb(ques[i].sc);

	for(int i=(sn-1); i>=1; i--)
		merge(i);

	for(int i=0; i<n; i++){
		pii qa = mp(a[i], 0), qb = mp(b[i], 0);

		if(qa >= qb)
			swap(qa, qb);

		int l = lb(ques, qa) - ques.begin();
		int r = lb(ques, qb) - ques.begin();
		
		l++;

		// cout << l << ' ' << r << ' ';

		int cnt=0, mx=0;
		if(l <= r)
			mx = get_max(1, 1, sn, l, r);

		// cout << mx << ' ';
		if(r < k)
			cnt = cnt_gte(1, 1, sn, r+1, k, mx);
		

		// cout << cnt << ": ";

		if(a[i] <= b[i] and l<=r)
			cnt++;

		if(cnt & 1)
			// cout << b[i] << endl;
			sm += b[i];
		else 
			// cout << a[i] << endl;
			sm += a[i];

	}

	cout << sm << endl;

	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void merge(int)':
fortune_telling2.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  while(pl < seg[lc].size() and pr < seg[rc].size()){
      |        ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:36:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  while(pl < seg[lc].size() and pr < seg[rc].size()){
      |                                ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:47:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  while(pl < seg[lc].size()){
      |        ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  while(pr < seg[rc].size()){
      |        ~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26460 KB Output is correct
2 Correct 8 ms 26460 KB Output is correct
3 Correct 9 ms 26504 KB Output is correct
4 Correct 9 ms 26460 KB Output is correct
5 Correct 8 ms 26460 KB Output is correct
6 Correct 8 ms 26460 KB Output is correct
7 Correct 8 ms 26460 KB Output is correct
8 Correct 7 ms 26460 KB Output is correct
9 Correct 7 ms 26460 KB Output is correct
10 Correct 7 ms 26572 KB Output is correct
11 Correct 7 ms 26588 KB Output is correct
12 Correct 8 ms 26460 KB Output is correct
13 Correct 8 ms 26460 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26460 KB Output is correct
2 Correct 8 ms 26460 KB Output is correct
3 Correct 9 ms 26504 KB Output is correct
4 Correct 9 ms 26460 KB Output is correct
5 Correct 8 ms 26460 KB Output is correct
6 Correct 8 ms 26460 KB Output is correct
7 Correct 8 ms 26460 KB Output is correct
8 Correct 7 ms 26460 KB Output is correct
9 Correct 7 ms 26460 KB Output is correct
10 Correct 7 ms 26572 KB Output is correct
11 Correct 7 ms 26588 KB Output is correct
12 Correct 8 ms 26460 KB Output is correct
13 Correct 8 ms 26460 KB Output is correct
14 Correct 19 ms 27992 KB Output is correct
15 Correct 34 ms 29408 KB Output is correct
16 Correct 48 ms 31096 KB Output is correct
17 Correct 62 ms 32720 KB Output is correct
18 Correct 62 ms 32836 KB Output is correct
19 Correct 61 ms 32832 KB Output is correct
20 Correct 65 ms 32720 KB Output is correct
21 Correct 57 ms 32716 KB Output is correct
22 Correct 45 ms 32212 KB Output is correct
23 Correct 46 ms 32208 KB Output is correct
24 Correct 49 ms 32380 KB Output is correct
25 Correct 46 ms 32476 KB Output is correct
26 Correct 49 ms 32732 KB Output is correct
27 Correct 63 ms 32740 KB Output is correct
28 Correct 55 ms 32728 KB Output is correct
29 Correct 63 ms 32684 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26460 KB Output is correct
2 Correct 8 ms 26460 KB Output is correct
3 Correct 9 ms 26504 KB Output is correct
4 Correct 9 ms 26460 KB Output is correct
5 Correct 8 ms 26460 KB Output is correct
6 Correct 8 ms 26460 KB Output is correct
7 Correct 8 ms 26460 KB Output is correct
8 Correct 7 ms 26460 KB Output is correct
9 Correct 7 ms 26460 KB Output is correct
10 Correct 7 ms 26572 KB Output is correct
11 Correct 7 ms 26588 KB Output is correct
12 Correct 8 ms 26460 KB Output is correct
13 Correct 8 ms 26460 KB Output is correct
14 Correct 19 ms 27992 KB Output is correct
15 Correct 34 ms 29408 KB Output is correct
16 Correct 48 ms 31096 KB Output is correct
17 Correct 62 ms 32720 KB Output is correct
18 Correct 62 ms 32836 KB Output is correct
19 Correct 61 ms 32832 KB Output is correct
20 Correct 65 ms 32720 KB Output is correct
21 Correct 57 ms 32716 KB Output is correct
22 Correct 45 ms 32212 KB Output is correct
23 Correct 46 ms 32208 KB Output is correct
24 Correct 49 ms 32380 KB Output is correct
25 Correct 46 ms 32476 KB Output is correct
26 Correct 49 ms 32732 KB Output is correct
27 Correct 63 ms 32740 KB Output is correct
28 Correct 55 ms 32728 KB Output is correct
29 Correct 63 ms 32684 KB Output is correct
30 Correct 114 ms 55480 KB Output is correct
31 Correct 183 ms 56264 KB Output is correct
32 Correct 284 ms 57404 KB Output is correct
33 Correct 446 ms 59332 KB Output is correct
34 Correct 97 ms 55240 KB Output is correct
35 Correct 452 ms 59504 KB Output is correct
36 Correct 455 ms 59336 KB Output is correct
37 Correct 453 ms 59340 KB Output is correct
38 Correct 434 ms 59244 KB Output is correct
39 Correct 442 ms 59332 KB Output is correct
40 Correct 297 ms 59096 KB Output is correct
41 Correct 438 ms 59252 KB Output is correct
42 Correct 455 ms 59336 KB Output is correct
43 Correct 190 ms 58564 KB Output is correct
44 Correct 189 ms 58468 KB Output is correct
45 Correct 180 ms 58572 KB Output is correct
46 Correct 227 ms 57388 KB Output is correct
47 Correct 234 ms 57124 KB Output is correct
48 Correct 329 ms 59336 KB Output is correct
49 Correct 318 ms 59424 KB Output is correct