Submission #36016

#	Time	Username	Problem	Language	Result	Execution time	Memory
36016		minkank	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	363 ms	78560 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n, m, a[N], b[N], c[N], last[21][3 * N], lg[3 * N], bit[3 * N];
vector<int> Value, Query[3 * N];
long long ans;

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

int get(int pos) {
	int res = 0;
	for(pos; pos < 3 * N; pos += pos & -pos) res += bit[pos];
	return res;
}

void getint(int &x) {
	x = 0;
	char c = getchar();
	while('0' > c || c > '9') c = getchar();
	while('0' <= c && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
}

int main() {
	getint(n); getint(m);
	lg[1] = 0;
	for(int i = 2; i < 3 * N; ++i) lg[i] = lg[i / 2] + 1;
	for(int i = 1; i <= n; ++i) getint(a[i]), getint(b[i]), Value.push_back(a[i]), Value.push_back(b[i]);
	for(int i = 1; i <= m; ++i) getint(c[i]), Value.push_back(c[i]);
	Value.push_back(0);
	sort(Value.begin(), Value.end());
	Value.resize(distance(Value.begin(), unique(Value.begin(), Value.end())));
	for(int i = 1; i <= n; ++i) 
		a[i] = lower_bound(Value.begin(), Value.end(), a[i]) - Value.begin() + 1,
		b[i] = lower_bound(Value.begin(), Value.end(), b[i]) - Value.begin() + 1;
	for(int i = 1; i <= m; ++i)
		c[i] = lower_bound(Value.begin(), Value.end(), c[i]) - Value.begin() + 1;
	for(int i = m; i >= 1; --i) if(!last[0][c[i]]) last[0][c[i]] = i;
	for(int i = 1; i <= 20; ++i) for(int j = 1; j < 3 * N; ++j)
		last[i][j] = max(last[i - 1][j], last[i - 1][j + (1 << (i - 1))]);
	for(int i = 1; i <= n; ++i) {
		if(a[i] == b[i]) {
			ans += Value[a[i] - 1];
			continue;
		}
		int mn = min(a[i], b[i]), mx = max(a[i], b[i]) - 1;
		int pos = max(last[lg[mx - mn + 1]][mn], last[lg[mx - mn + 1]][mx - (1 << lg[mx - mn + 1]) + 1]);
		Query[pos].push_back(i);
	}
	for(int i = m; i >= 0; --i) {
		for(auto j: Query[i]) {
			if(i && a[j] < b[j]) swap(a[j], b[j]);
			if(get(a[j]) & 1) ans += Value[b[j] - 1];
			else ans += Value[a[j] - 1];
		}
		upd(c[i]);
	}
	printf("%lld", ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void upd(int)':
fortune_telling2.cpp:11:9: warning: statement has no effect [-Wunused-value]
  for(pos; pos > 0; pos -= pos & -pos) bit[pos]++;
         ^
fortune_telling2.cpp: In function 'int get(int)':
fortune_telling2.cpp:16:9: warning: statement has no effect [-Wunused-value]
  for(pos; pos < 3 * N; pos += pos & -pos) res += bit[pos];
         ^

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65