oj.uz

Submission #33062

# Submission time Handle Problem Language Result Execution time Memory
33062 2017-10-19T15:28:05 Z aome Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 299 ms 33488 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
const int N = 200005;

int n, k, a[N], b[N], t[N];
int lg2[N], rmq[20][N];
int bit[N], res[N];
vector<ii> go, query[N];

int get(int l, int r) {
	int k = lg2[r - l + 1];
	return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

void upd(int x) {
	for (x; x > 0; x -= x & -x) bit[x]++;
}

int get(int x) {
	int ret = 0; for (x; x <= k; x += x & -x) ret += bit[x]; return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
	}
	for (int i = 1; i <= k; ++i) {
		cin >> t[i], go.push_back(ii(t[i], i)); 
	}
	sort(go.begin(), go.end());
	for (int i = 2; i <= k; ++i) lg2[i] = lg2[i >> 1] + 1;
	for (int i = 0; i < k; ++i) rmq[0][i] = go[i].second;
	for (int i = 1; i < 18; ++i) {
		for (int j = 0; j + (1 << i) - 1 < k; ++j) {
			rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		int l = min(a[i], b[i]), r = max(a[i], b[i]);
		l = lower_bound(go.begin(), go.end(), ii(l, 0)) - go.begin();
		r = lower_bound(go.begin(), go.end(), ii(r, 0)) - go.begin() - 1;
		int tmp = 0;
		if (l <= r) {
			tmp = get(l, r);
			if (a[i] < b[i]) swap(a[i], b[i]);
		}
		query[r + 1].push_back(ii(i, tmp + 1));
	} 
	for (int i = k - 1; i >= 0; --i) {
		upd(go[i].second);
		for (auto j : query[i]) res[j.first] = get(j.second) & 1;
	}
	long long sum = 0;
 	for (int i = 1; i <= n; ++i) {
 		sum += (!res[i] ? a[i] : b[i]);
 	}
 	cout << sum << '\n';
}

Compilation message

fortune_telling2.cpp: In function 'void upd(int)':
fortune_telling2.cpp:18:8: warning: statement has no effect [-Wunused-value]
  for (x; x > 0; x -= x & -x) bit[x]++;
        ^
fortune_telling2.cpp: In function 'int get(int)':
fortune_telling2.cpp:22:21: warning: statement has no effect [-Wunused-value]
  int ret = 0; for (x; x <= k; x += x & -x) ret += bit[x]; return ret;
                     ^

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27472 KB Output is correct
2 Correct 26 ms 27736 KB Output is correct
3 Correct 26 ms 28000 KB Output is correct
4 Correct 46 ms 28388 KB Output is correct
5 Correct 46 ms 28388 KB Output is correct
6 Correct 39 ms 28388 KB Output is correct
7 Correct 73 ms 28388 KB Output is correct
8 Correct 56 ms 28256 KB Output is correct
9 Correct 16 ms 28388 KB Output is correct
10 Correct 26 ms 28388 KB Output is correct
11 Correct 39 ms 28520 KB Output is correct
12 Correct 33 ms 28256 KB Output is correct
13 Correct 36 ms 28256 KB Output is correct
14 Correct 46 ms 28256 KB Output is correct
15 Correct 29 ms 28256 KB Output is correct
16 Correct 33 ms 28388 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 30292 KB Output is correct
2 Correct 113 ms 30452 KB Output is correct
3 Correct 173 ms 31376 KB Output is correct
4 Correct 283 ms 32828 KB Output is correct
5 Correct 56 ms 30292 KB Output is correct
6 Correct 276 ms 32828 KB Output is correct
7 Correct 269 ms 32828 KB Output is correct
8 Correct 299 ms 32828 KB Output is correct
9 Correct 266 ms 32564 KB Output is correct
10 Correct 276 ms 32960 KB Output is correct
11 Correct 189 ms 31772 KB Output is correct
12 Correct 263 ms 32828 KB Output is correct
13 Correct 279 ms 32960 KB Output is correct
14 Correct 126 ms 31840 KB Output is correct
15 Correct 129 ms 31680 KB Output is correct
16 Correct 156 ms 31460 KB Output is correct
17 Correct 146 ms 32828 KB Output is correct
18 Correct 146 ms 33488 KB Output is correct
19 Correct 216 ms 32432 KB Output is correct
20 Correct 266 ms 32432 KB Output is correct