Submission #117167

#	Time	Username	Problem	Language	Result	Execution time	Memory
117167		Just_Solve_The_Problem	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	430 ms	22500 KiB

fortune_telling2

#include <bits/stdc++.h>

#define ll long long
#define ok puts("ok");

using namespace std;

const int N = (int)4e5 + 7;

struct T {
	int tree[N * 4];
	T() {
		memset(tree, -1, sizeof tree);
	}
	void upd(int pos, int val, int v = 1, int tl = -1, int tr = 4e5) {
		if (tl == tr) {
			tree[v] = val;
			return ;
		}
		int mid = (tl + tr) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, tl, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, tr);
		}
		tree[v] = max(tree[v + v], tree[v + v + 1]);
	}
	int get(int l, int r, int v = 1, int tl = -1, int tr = 4e5) {
		if (tl > r || tr < l) return -1;
		if (l <= tl && tr <= r) return tree[v];
		int mid = (tl + tr) >> 1;
		return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
	}
};
T tr;

struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val) {
		pos = max(pos, 0);
		while (pos < N) {
			tree[pos] += val;
			pos = pos | (pos + 1);
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
};
fen bit1;

int n, k;
int flip[N];
int a[N], b[N], q[N], border[N];
ll sum = 0;

main() {
	scanf("%d %d", &n, &k);
	vector<int> vec;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i], &b[i]);
		vec.push_back(a[i]);
		vec.push_back(b[i]);
		if (a[i] > b[i]) {
			swap(a[i], b[i]);
			flip[i] = 1;
		}
	}
	for (int i = 1; i <= k; i++) {
		scanf("%d", &q[i]);
	}
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
		b[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin();
	}
	for (int i = 1; i <= k; i++) {
		q[i] = upper_bound(vec.begin(), vec.end(), q[i]) - vec.begin() - 1;
		tr.upd(q[i], i);
	}
	vector<pair<int, int>> v1;
	for (int i = 1; i <= n; i++) {
		border[i] = tr.get(a[i], b[i] - 1);
		v1.push_back({border[i] + 1, i});
		if (border[i] > 0) {
			flip[i] = 1;
		}
	}
	sort(v1.begin(), v1.end());
	int sz = k;
	for (int i = v1.size() - 1; i >= 0; i--) {
		while (sz >= v1[i].first) {
			bit1.upd(q[sz], 1);
			sz--;
		}
		flip[v1[i].second] ^= ((k - sz - bit1.get(b[v1[i].second] - 1)) & 1);
	}
	for (int i = 1; i <= n; i++) {
		sum += (flip[i] ? vec[b[i]] : vec[a[i]]);
	}
	printf("%lld\n", sum);
}

Compilation message (stderr)

fortune_telling2.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q[i]);
   ~~~~~^~~~~~~~~~~~~

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