oj.uz

Submission #36048

# Submission time Handle Problem Language Result Execution time Memory
36048 2017-12-04T16:52:19 Z ToMoClone Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 2000 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(){
	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) < 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 << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 65448 KB Output is correct
2 Correct 183 ms 65448 KB Output is correct
3 Correct 189 ms 65448 KB Output is correct
4 Correct 206 ms 65448 KB Output is correct
5 Correct 193 ms 65448 KB Output is correct
6 Correct 193 ms 65448 KB Output is correct
7 Correct 199 ms 65448 KB Output is correct
8 Correct 186 ms 65448 KB Output is correct
9 Correct 203 ms 65448 KB Output is correct
10 Correct 183 ms 65448 KB Output is correct
11 Correct 189 ms 65448 KB Output is correct
12 Correct 193 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 219 ms 66768 KB Output is correct
2 Correct 289 ms 68088 KB Output is correct
3 Correct 346 ms 69540 KB Output is correct
4 Correct 439 ms 70992 KB Output is correct
5 Correct 433 ms 70992 KB Output is correct
6 Correct 383 ms 70992 KB Output is correct
7 Correct 393 ms 70992 KB Output is correct
8 Correct 423 ms 70992 KB Output is correct
9 Correct 326 ms 69144 KB Output is correct
10 Correct 306 ms 68088 KB Output is correct
11 Correct 316 ms 67428 KB Output is correct
12 Correct 369 ms 69672 KB Output is correct
13 Correct 366 ms 68748 KB Output is correct
14 Correct 393 ms 69144 KB Output is correct
15 Correct 403 ms 69144 KB Output is correct
16 Correct 416 ms 70068 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 75612 KB Output is correct
2 Correct 896 ms 79440 KB Output is correct
3 Correct 1233 ms 84060 KB Output is correct
4 Execution timed out 2000 ms 93432 KB Execution timed out
5 Halted 0 ms 0 KB -