oj.uz

Submission #36049

# Submission time Handle Problem Language Result Execution time Memory
36049 2017-12-04T16:56:22 Z ToMoClone Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 666 ms 95928 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 = 200005;

int bit[N], Last[N], On[N], Arr[5 * 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) < 5 * N; ++j)
		for(int i = 1; i < 5 * 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 333 ms 85764 KB Output is correct
2 Correct 319 ms 85764 KB Output is correct
3 Correct 339 ms 85764 KB Output is correct
4 Correct 319 ms 85764 KB Output is correct
5 Correct 333 ms 85764 KB Output is correct
6 Correct 323 ms 85764 KB Output is correct
7 Correct 316 ms 85764 KB Output is correct
8 Correct 336 ms 85764 KB Output is correct
9 Correct 313 ms 85764 KB Output is correct
10 Correct 343 ms 85764 KB Output is correct
11 Correct 299 ms 85764 KB Output is correct
12 Correct 316 ms 85764 KB Output is correct
13 Correct 309 ms 85764 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 87084 KB Output is correct
2 Correct 413 ms 88404 KB Output is correct
3 Correct 486 ms 89856 KB Output is correct
4 Correct 493 ms 91308 KB Output is correct
5 Correct 513 ms 91308 KB Output is correct
6 Correct 529 ms 91308 KB Output is correct
7 Correct 473 ms 91308 KB Output is correct
8 Correct 446 ms 91308 KB Output is correct
9 Correct 446 ms 89460 KB Output is correct
10 Correct 406 ms 88404 KB Output is correct
11 Correct 399 ms 87744 KB Output is correct
12 Correct 413 ms 89988 KB Output is correct
13 Correct 396 ms 89064 KB Output is correct
14 Correct 439 ms 89460 KB Output is correct
15 Correct 413 ms 89460 KB Output is correct
16 Correct 426 ms 90384 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 666 ms 95928 KB Output isn't correct
2 Halted 0 ms 0 KB -