Submission #35875

#	Time	Username	Problem	Language	Result	Execution time	Memory
35875		UncleGrandpa925	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	133 ms	43400 KiB

fortune_telling2

/*input
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/
#include <bits/stdc++.h>

#define _GLIBCXX_DEBUG

using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 200005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
struct data {
	int fi, se, state;
	data(int _fi, int _se, int _state): fi(_fi), se(_se), state(_state) {};
};

bool bySE(data x, data y) {
	return x.se < y.se;
}

int n, q;
vector<data> a;
vector<pair<int, int> > b;
array<int, N> tree;
array<array<int, 20>, N> rmq;
array<int, N> lg2;


void update(int i, int val) {
	for (; i; i -= i & -i) tree[i] += val;
}

int get(int i) {
	int ret = 0;
	for (; i <= n; i += i & -i) ret += tree[i];
	return ret;
}

void initRMQ() {
	for (int i = 1; i < N; i++) lg2[i] = log2(i);
	for (int i = 1; i <= q; i++)
		rmq[i][0] = b[i - 1].se;
	for (int k = 1; k < 20; k++) {
		for (int i = 1; i + (1 << k) - 1 <= q; i++) {
			rmq[i][k] = max(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
		}
	}
}

int getRMQ(int l, int r) {
	if (l > r) return -1;
	int len = lg2[r - l + 1];
	return max(rmq[l][len], rmq[r - (1 << len) + 1][len]);
}

void solve() {
	int it = b.size() - 1;
	int ans = 0;
	for (int i = (signed)a.size() - 1; i >= 0; i--) {
		while (it >= 0 && b[it].fi >= a[i].se) {
			update(b[it].se, 1);
			it--;
		}
		if (a[i].fi == a[i].se) {
			ans += a[i].fi;
			continue;
		}
		int l = lower_bound(b.begin(), b.end(), mp(a[i].fi, -1LL)) - b.begin();
		int r = (signed)(upper_bound(b.begin(), b.end(), mp(a[i].se, -1LL)) - b.begin()) - 1;
		int rec = getRMQ(l + 1, r + 1);
		if (rec == -1) {
			if (a[i].state == 1) ans += a[i].se;
			else ans += a[i].fi;
			continue;
		}
		a[i].state = 1;
		rec++;
		rec = get(rec);
		if (rec % 2) a[i].state = 0;
		if (a[i].state == 1) ans += a[i].se;
		else ans += a[i].fi;
	}
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int x, y; cin >> x >> y;
		if (x < y) a.push_back(data(x, y, 0));
		else a.push_back(data(y, x, 1));
	}
	sort(a.begin(), a.end(), bySE);
	for (int i = 1; i <= q; i++) {
		int t; cin >> t;
		b.push_back(mp(t, i));
	}
	sort(b.begin(), b.end());
	initRMQ();
	solve();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
fortune_telling2.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
fortune_telling2.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^

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