oj.uz

Submission #377504

# Submission time Handle Problem Language Result Execution time Memory
377504 2021-03-14T09:24:28 Z reymontada61 Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 1631 ms 10048 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, k, ans;
vector<pair<pair<int, int>, int>> crs; 
vector<pair<int, int>> qs;

const int MXN = 40005;

int seg[MXN * 4];

void build(int ind, int l, int r) {
	if (l == r) {
		seg[ind] = qs[l].second;
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
	seg[ind] = max(seg[ind*2], seg[ind*2+1]);
}

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return seg[ind];
	if (ql > r || qr < l) return -1;
	int m = (l + r) / 2;
	return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
}

signed main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> k;
	for (int i=0; i<n; i++) {
		int a, b;
		cin >> a >> b;
		
		if (a == b) {
			ans += a;
			continue;
		}
		
		int s = 0;
		if (a > b) {
			swap(a, b); s = 1;
		}
		
		crs.push_back({{a, b}, s});
		
	}
	
	n = crs.size();
	
	for (int i=0; i<k; i++) {
		int x;
		cin >> x;
		qs.push_back({x, i});
	}
	
	sort(qs.begin(), qs.end());
	
	build(1, 0, k-1);
	
	for (auto x: crs) {
		int a = x.first.first, b = x.first.second;
		
		int e = lower_bound(qs.begin(), qs.end(), make_pair(a, 0ll)) - qs.begin();
		int f = upper_bound(qs.begin(), qs.end(), make_pair(b-1, k)) - qs.begin() - 1;
		
		int ls = query(1, 0, k-1, e, f);
		
		int up = x.second;
		if (ls != -1) up = 1;
		
		int flips = 0;
		
		for (int j=0; j<qs.size(); j++) {
			if (qs[j].first >= b && qs[j].second > ls) flips++;
		}
		
		if (flips % 2 == 1) up = 1 - up;
		
		if (up) ans += b;
		else ans += a;
		
	}
	
	cout << ans << endl;

}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:79:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int j=0; j<qs.size(); j++) {
      |                 ~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 105 ms 1512 KB Output is correct
15 Correct 399 ms 2916 KB Output is correct
16 Correct 908 ms 3496 KB Output is correct
17 Correct 1631 ms 5204 KB Output is correct
18 Correct 1584 ms 5204 KB Output is correct
19 Correct 1573 ms 5216 KB Output is correct
20 Correct 1562 ms 5088 KB Output is correct
21 Correct 1574 ms 5216 KB Output is correct
22 Correct 1565 ms 4704 KB Output is correct
23 Correct 1548 ms 4704 KB Output is correct
24 Correct 1600 ms 4832 KB Output is correct
25 Correct 1604 ms 4880 KB Output is correct
26 Correct 1369 ms 4960 KB Output is correct
27 Correct 1538 ms 5208 KB Output is correct
28 Correct 1518 ms 5284 KB Output is correct
29 Correct 1529 ms 5216 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 105 ms 1512 KB Output is correct
15 Correct 399 ms 2916 KB Output is correct
16 Correct 908 ms 3496 KB Output is correct
17 Correct 1631 ms 5204 KB Output is correct
18 Correct 1584 ms 5204 KB Output is correct
19 Correct 1573 ms 5216 KB Output is correct
20 Correct 1562 ms 5088 KB Output is correct
21 Correct 1574 ms 5216 KB Output is correct
22 Correct 1565 ms 4704 KB Output is correct
23 Correct 1548 ms 4704 KB Output is correct
24 Correct 1600 ms 4832 KB Output is correct
25 Correct 1604 ms 4880 KB Output is correct
26 Correct 1369 ms 4960 KB Output is correct
27 Correct 1538 ms 5208 KB Output is correct
28 Correct 1518 ms 5284 KB Output is correct
29 Correct 1529 ms 5216 KB Output is correct
30 Runtime error 54 ms 10048 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -