Submission #33062

#	Time	Username	Problem	Language	Result	Execution time	Memory
33062		aome	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	299 ms	33488 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65