oj.uz

Submission #405140

# Submission time Handle Problem Language Result Execution time Memory
405140 2021-05-15T18:26:56 Z saarang123 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 721 ms 41540 KB 
#include <bits/stdc++.h>
using namespace std;
const int MXN = 700 * 1000 + 3;
int tree[MXN << 2], a[MXN], b[MXN], t[MXN], oga[MXN], ogb[MXN];
vector<int> coord, q[MXN];
int n, k, sz;

function<int(int, int)> comb = [] (int x, int y) {
	return max(x, y);
};

void update(int v, int tl, int tr, int pos, int x) {
	if(tl == tr)
		tree[v] = comb(tree[v], x);
	else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			update(v << 1, tl, tm, pos, x);
		else
			update(v << 1|1, tm + 1, tr, pos, x);
		tree[v] = comb(tree[v << 1], tree[v << 1|1]);
	}
}

void upd(int pos, int x) {
	update(1, 1, MXN - 2, pos, x);
}

int query(int v, int tl, int tr, int l, int r) {
	if(l > r)
		return 0;
	if(l <= tl && tr <= r)
		return tree[v];
	int tm = (tl + tr) >> 1;
	return comb(query(v << 1, tl, tm, l, min(tm, r)),
				query(v << 1|1, tm + 1, tr, max(tm + 1, l), r));
}

int query(int l, int r) {
	return query(1, 1, MXN - 2, l, r);
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
    	cin >> oga[i] >> ogb[i];
    	coord.push_back(oga[i]);
    	coord.push_back(ogb[i]);
    }
    for(int i = 1; i <= k; i++) {
    	cin >> t[i];
    	coord.push_back(t[i]);
    }

    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
    sz = coord.size();
    auto id = [&] (int x) {
    	return upper_bound(coord.begin(), coord.end(), x) - coord.begin();
    };
    for(int i = 1; i <= n; i++) {
    	a[i] = id(oga[i]);
    	b[i] = id(ogb[i]);
    }
    for(int i = 1; i <= k; i++) {
    	t[i] = id(t[i]);
    	upd(t[i], i);
    }

    for(int i = 1; i <= n; i++) {
    	int x = query(min(a[i], b[i]), max(a[i], b[i]) - 1);
    	q[x].push_back(i);
    }
    memset(tree, 0, sizeof tree);
    comb = [&] (int x, int y) {
    	return x + y;
    };
    long long ans = 0;
    for(int x = k; x >= 0; x--) {
    	for(int i : q[x]) {
    		int parity = query(max(a[i], b[i]), sz) & 1;
    		if(x)
    			parity ^= a[i] < b[i];
    		ans += parity ? ogb[i] : oga[i];
    	}
    	upd(t[x], 1);
    }

    cout << ans << '\n';
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27756 KB Output is correct
2 Correct 17 ms 27724 KB Output is correct
3 Correct 18 ms 27784 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 18 ms 27776 KB Output is correct
6 Correct 17 ms 27776 KB Output is correct
7 Correct 18 ms 27696 KB Output is correct
8 Correct 18 ms 27796 KB Output is correct
9 Correct 17 ms 27724 KB Output is correct
10 Correct 17 ms 27696 KB Output is correct
11 Correct 18 ms 27752 KB Output is correct
12 Correct 17 ms 27688 KB Output is correct
13 Correct 17 ms 27776 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27756 KB Output is correct
2 Correct 17 ms 27724 KB Output is correct
3 Correct 18 ms 27784 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 18 ms 27776 KB Output is correct
6 Correct 17 ms 27776 KB Output is correct
7 Correct 18 ms 27696 KB Output is correct
8 Correct 18 ms 27796 KB Output is correct
9 Correct 17 ms 27724 KB Output is correct
10 Correct 17 ms 27696 KB Output is correct
11 Correct 18 ms 27752 KB Output is correct
12 Correct 17 ms 27688 KB Output is correct
13 Correct 17 ms 27776 KB Output is correct
14 Correct 41 ms 28176 KB Output is correct
15 Correct 71 ms 28440 KB Output is correct
16 Correct 103 ms 28744 KB Output is correct
17 Correct 132 ms 29248 KB Output is correct
18 Correct 128 ms 29236 KB Output is correct
19 Correct 136 ms 29236 KB Output is correct
20 Correct 126 ms 29172 KB Output is correct
21 Correct 130 ms 29392 KB Output is correct
22 Correct 111 ms 29120 KB Output is correct
23 Correct 120 ms 29252 KB Output is correct
24 Correct 109 ms 29232 KB Output is correct
25 Correct 111 ms 29336 KB Output is correct
26 Correct 106 ms 29124 KB Output is correct
27 Correct 120 ms 29256 KB Output is correct
28 Correct 114 ms 29292 KB Output is correct
29 Correct 121 ms 29252 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27756 KB Output is correct
2 Correct 17 ms 27724 KB Output is correct
3 Correct 18 ms 27784 KB Output is correct
4 Correct 17 ms 27696 KB Output is correct
5 Correct 18 ms 27776 KB Output is correct
6 Correct 17 ms 27776 KB Output is correct
7 Correct 18 ms 27696 KB Output is correct
8 Correct 18 ms 27796 KB Output is correct
9 Correct 17 ms 27724 KB Output is correct
10 Correct 17 ms 27696 KB Output is correct
11 Correct 18 ms 27752 KB Output is correct
12 Correct 17 ms 27688 KB Output is correct
13 Correct 17 ms 27776 KB Output is correct
14 Correct 41 ms 28176 KB Output is correct
15 Correct 71 ms 28440 KB Output is correct
16 Correct 103 ms 28744 KB Output is correct
17 Correct 132 ms 29248 KB Output is correct
18 Correct 128 ms 29236 KB Output is correct
19 Correct 136 ms 29236 KB Output is correct
20 Correct 126 ms 29172 KB Output is correct
21 Correct 130 ms 29392 KB Output is correct
22 Correct 111 ms 29120 KB Output is correct
23 Correct 120 ms 29252 KB Output is correct
24 Correct 109 ms 29232 KB Output is correct
25 Correct 111 ms 29336 KB Output is correct
26 Correct 106 ms 29124 KB Output is correct
27 Correct 120 ms 29256 KB Output is correct
28 Correct 114 ms 29292 KB Output is correct
29 Correct 121 ms 29252 KB Output is correct
30 Correct 238 ms 29628 KB Output is correct
31 Correct 329 ms 30904 KB Output is correct
32 Correct 457 ms 32120 KB Output is correct
33 Correct 714 ms 41100 KB Output is correct
34 Correct 220 ms 31292 KB Output is correct
35 Correct 700 ms 41088 KB Output is correct
36 Correct 711 ms 40876 KB Output is correct
37 Correct 689 ms 40812 KB Output is correct
38 Correct 721 ms 40964 KB Output is correct
39 Correct 699 ms 40972 KB Output is correct
40 Correct 676 ms 41540 KB Output is correct
41 Correct 692 ms 40880 KB Output is correct
42 Correct 699 ms 40856 KB Output is correct
43 Correct 550 ms 41016 KB Output is correct
44 Correct 538 ms 41064 KB Output is correct
45 Correct 548 ms 40980 KB Output is correct
46 Correct 537 ms 39084 KB Output is correct
47 Correct 498 ms 38832 KB Output is correct
48 Correct 588 ms 41080 KB Output is correct
49 Correct 561 ms 41296 KB Output is correct