Submission #36098

#	Time	Username	Problem	Language	Result	Execution time	Memory
36098		UncleGrandpa925	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	419 ms	50948 KiB

fortune_telling2

/*input
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 200010
#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) {};
};

int n, q;
vector<data> a;
vector<pair<int, int> > query;
int tree[N];
int rmq[N][20];
int lg2[N];

bool cmp(data x, data y) {
	return x.se > y.se;
}

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

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

void initRMQ() {
	for (int i = 1; i <= q; i++) rmq[i][0] = query[i].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 0;
	int len = lg2[r - l + 1]; // opt
	return max(rmq[l][len], rmq[r - (1 << len) + 1][len]);
}

int getLast(int l, int r) {
	auto itleft = lower_bound(query.begin(), query.end(), mp(l, -1LL));
	auto itRight = lower_bound(query.begin(), query.end(), mp(r, -1LL));
	return getRMQ(itleft - query.begin(), min(q, (int)(itRight - query.begin() - 1)));
}

void solve() {
	int ans = 0;
	int it = query.size() - 1;
	for (int i = 0; i < a.size(); i++) {
		while (it >= 1 && query[it].fi >= a[i].se) {
			update(query[it].se, 1);
			it--;
		}
		int last = getLast(a[i].fi, a[i].se);
		if (last) a[i].state = 1;
		last++;
		int rec = get(last);
		if (rec % 2) a[i].state ^= 1;
		if (a[i].state == 0) ans += a[i].fi;
		else ans += a[i].se;
	}
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef in1code
	freopen("1test.inp", "r", stdin);
#endif
	for (int i = 1; i <= N - 5; i++) lg2[i] = log2(i);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int u, v; cin >> u >> v;
		if (u < v) a.push_back(data(u, v, 0));
		else a.push_back(data(v, u, 1));
	}
	sort(a.begin(), a.end(), cmp);
	query.push_back(mp(-1, -1));
	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		query.push_back(mp(t, i + 1));
	}
	sort(query.begin(), query.end());
	initRMQ();
	solve();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
fortune_telling2.cpp:24: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:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^

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