oj.uz

Submission #36046

# Submission time Handle Problem Language Result Execution time Memory
36046 2017-12-04T16:51:00 Z ToMoClone Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 616 ms 64676 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[3 * 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(){
	cin >> n >> k;
	for(int i = 1; i <= n; ++i){
		cin >> 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){
		cin >> 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) < 3 * N; ++j)
		for(int i = 1; i < 3 * 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 << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 54512 KB Output is correct
2 Correct 179 ms 54512 KB Output is correct
3 Correct 206 ms 54512 KB Output is correct
4 Correct 196 ms 54512 KB Output is correct
5 Correct 193 ms 54512 KB Output is correct
6 Correct 206 ms 54512 KB Output is correct
7 Correct 193 ms 54512 KB Output is correct
8 Correct 186 ms 54512 KB Output is correct
9 Correct 189 ms 54512 KB Output is correct
10 Correct 179 ms 54512 KB Output is correct
11 Correct 179 ms 54512 KB Output is correct
12 Correct 196 ms 54512 KB Output is correct
13 Correct 176 ms 54512 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 55832 KB Output is correct
2 Correct 269 ms 57152 KB Output is correct
3 Correct 329 ms 58604 KB Output is correct
4 Correct 373 ms 60056 KB Output is correct
5 Correct 449 ms 60056 KB Output is correct
6 Correct 406 ms 60056 KB Output is correct
7 Correct 406 ms 60056 KB Output is correct
8 Correct 433 ms 60056 KB Output is correct
9 Correct 326 ms 58208 KB Output is correct
10 Correct 293 ms 57152 KB Output is correct
11 Correct 319 ms 56492 KB Output is correct
12 Correct 356 ms 58736 KB Output is correct
13 Correct 346 ms 57812 KB Output is correct
14 Correct 356 ms 58208 KB Output is correct
15 Correct 323 ms 58208 KB Output is correct
16 Correct 379 ms 59132 KB Output is correct

Subtask #3
0 / 65.0

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