oj.uz

Submission #377507

# Submission time Handle Problem Language Result Execution time Memory
377507 2021-03-14T09:26:22 Z reymontada61 Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 1125 ms 7892 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=f+1; j<qs.size(); j++) {
			if (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:20: 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=f+1; j<qs.size(); j++) {
      |                   ~^~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 48 ms 1256 KB Output is correct
15 Correct 163 ms 2148 KB Output is correct
16 Correct 355 ms 2660 KB Output is correct
17 Correct 612 ms 4064 KB Output is correct
18 Correct 617 ms 4028 KB Output is correct
19 Correct 565 ms 4064 KB Output is correct
20 Correct 901 ms 3936 KB Output is correct
21 Correct 158 ms 4064 KB Output is correct
22 Correct 472 ms 4064 KB Output is correct
23 Correct 615 ms 4028 KB Output is correct
24 Correct 826 ms 3936 KB Output is correct
25 Correct 369 ms 3936 KB Output is correct
26 Correct 881 ms 3872 KB Output is correct
27 Correct 963 ms 4028 KB Output is correct
28 Correct 1125 ms 3936 KB Output is correct
29 Correct 995 ms 4028 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 48 ms 1256 KB Output is correct
15 Correct 163 ms 2148 KB Output is correct
16 Correct 355 ms 2660 KB Output is correct
17 Correct 612 ms 4064 KB Output is correct
18 Correct 617 ms 4028 KB Output is correct
19 Correct 565 ms 4064 KB Output is correct
20 Correct 901 ms 3936 KB Output is correct
21 Correct 158 ms 4064 KB Output is correct
22 Correct 472 ms 4064 KB Output is correct
23 Correct 615 ms 4028 KB Output is correct
24 Correct 826 ms 3936 KB Output is correct
25 Correct 369 ms 3936 KB Output is correct
26 Correct 881 ms 3872 KB Output is correct
27 Correct 963 ms 4028 KB Output is correct
28 Correct 1125 ms 3936 KB Output is correct
29 Correct 995 ms 4028 KB Output is correct
30 Runtime error 53 ms 7892 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -