oj.uz

Submission #36051

# Submission time Handle Problem Language Result Execution time Memory
36051 2017-12-04T16:57:19 Z ToMoClone Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1969 ms 93432 KB 
/*input
5 3
4 6
9 1
8 8
4 2
3 7
8 2 9
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 600005;

int bit[N], Last[N], On[N], Arr[N][20], n, k;
pair<int, int> Query[N], a[N];
map<int, int> Label;

void update(int index, int val){
	while(index < N) bit[index] += val, index += index & (-index);
}

int get(int index){
	int res = 0;
	while(index > 0) res += bit[index], index -= index & (-index);
	return res;
}

int Rmq(int l, int r){
	if(l > r) return 0;
	int dist = (int)log2(r - l + 1);
	return max(Arr[l][dist], Arr[r - (1 << dist) + 1][dist]);
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i){
		scanf("%d%d", &a[i].first, &a[i].second);
		Label[a[i].first] = 1, Label[a[i].second] = 1;
	}
	sort(a + 1, a + n + 1, [&](pair<int, int> &x, pair<int, int> &y){
		if(max(x.first, x.second) != max(y.first, y.second))
			return max(x.first, x.second) < max(y.first, y.second);
		return min(x.first, x.second) < min(y.first, y.second);
	});

	for(int i = 1; i <= n; ++i){
		On[i] = (a[i].first > a[i].second);
		if(On[i] == 0) swap(a[i].first, a[i].second);
	}

	Query[k + 1] = make_pair(1000000007, 0);
	for(int i = 1; i <= k; ++i){
		scanf("%d", &Query[i].first);
		Query[i].second = i;
		Label[Query[i].first] = 1;
	}
	sort(Query + 1, Query + k + 1);

	int cnt = 0;
	for(auto it = Label.begin(); it != Label.end(); ++it)
		it->second = ++cnt;

	for(int i = 1; i <= k; ++i)
		Arr[Label[Query[i].first]][0] = Query[i].second;

	for(int j = 1; (1 << j) < N; ++j)
		for(int i = 1; i < N; ++i)
			Arr[i][j] = max(Arr[i][j - 1], Arr[min(i + (1 << (j - 1)), N - 1)][j - 1]);

	for(int i = 1; i <= n; ++i){
		int l = Label.lower_bound(a[i].second)->second;
		int r = (--Label.lower_bound(a[i].first))->second;
		Last[i] = Rmq(l, r);
	}

	int64_t l = 1, ans = 0;
	for(int i = 1; i <= n; ++i){
		while(Query[l].first < a[i].first) update(Query[l++].second, 1);
		if(Last[i] != 0) On[i] = 1 ^ ((k - Last[i] - (get(N - 1) - get(Last[i]))) & 1);
			else On[i] ^= (k - get(N - 1)) & 1;
		ans += On[i] ? a[i].first : a[i].second;
	}

	cout << ans << '\n';
	// cerr << fixed << setprecision(20) << (double)(1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:37:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
fortune_telling2.cpp:39:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].first, &a[i].second);
                                           ^
fortune_telling2.cpp:55:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Query[i].first);
                               ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 65448 KB Output is correct
2 Correct 206 ms 65448 KB Output is correct
3 Correct 209 ms 65448 KB Output is correct
4 Correct 213 ms 65448 KB Output is correct
5 Correct 193 ms 65448 KB Output is correct
6 Correct 229 ms 65448 KB Output is correct
7 Correct 199 ms 65448 KB Output is correct
8 Correct 226 ms 65448 KB Output is correct
9 Correct 193 ms 65448 KB Output is correct
10 Correct 193 ms 65448 KB Output is correct
11 Correct 206 ms 65448 KB Output is correct
12 Correct 189 ms 65448 KB Output is correct
13 Correct 196 ms 65448 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 66768 KB Output is correct
2 Correct 259 ms 68088 KB Output is correct
3 Correct 313 ms 69540 KB Output is correct
4 Correct 376 ms 70992 KB Output is correct
5 Correct 389 ms 70992 KB Output is correct
6 Correct 363 ms 70992 KB Output is correct
7 Correct 413 ms 70992 KB Output is correct
8 Correct 423 ms 70992 KB Output is correct
9 Correct 363 ms 69144 KB Output is correct
10 Correct 319 ms 68088 KB Output is correct
11 Correct 283 ms 67428 KB Output is correct
12 Correct 369 ms 69672 KB Output is correct
13 Correct 353 ms 68748 KB Output is correct
14 Correct 329 ms 69144 KB Output is correct
15 Correct 376 ms 69144 KB Output is correct
16 Correct 386 ms 70068 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 75612 KB Output is correct
2 Correct 786 ms 79440 KB Output is correct
3 Correct 1099 ms 84060 KB Output is correct
4 Correct 1899 ms 93432 KB Output is correct
5 Correct 566 ms 74688 KB Output is correct
6 Correct 1863 ms 93432 KB Output is correct
7 Correct 1943 ms 93432 KB Output is correct
8 Correct 1969 ms 93432 KB Output is correct
9 Correct 1669 ms 93432 KB Output is correct
10 Correct 1669 ms 93432 KB Output is correct
11 Correct 1623 ms 93432 KB Output is correct
12 Correct 1599 ms 93432 KB Output is correct
13 Correct 1646 ms 93432 KB Output is correct
14 Correct 1066 ms 93432 KB Output is correct
15 Correct 969 ms 93432 KB Output is correct
16 Correct 989 ms 93432 KB Output is correct
17 Correct 889 ms 79440 KB Output is correct
18 Correct 799 ms 74688 KB Output is correct
19 Correct 1183 ms 84060 KB Output is correct
20 Correct 1123 ms 84060 KB Output is correct