Submission #364406

#	Time	Username	Problem	Language	Result	Execution time	Memory
364406		Kevin_Zhang_TW	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	2 ms	364 KiB

fortune_telling2

//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) {  cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 200010, SQ = 600;

int a[MAX_N], b[MAX_N], mt[MAX_N], n, m;

struct ASK {
	int a, b, c, d;
}qry[MAX_N];
bool operator < (ASK a, ASK b) {
	int l1 = a.c, r1 = a.d;
	int l2 = b.c, r2 = b.d;
	int aid = l1 / SQ, bid = l2 / SQ;
	if (aid != bid) return aid < bid;
	return (r1 < r2) ^ (aid & 1);
}
pair<int,int> lisan[MAX_N];

struct DS {
	int sum[SQ], cnt[MAX_N], all, n;
	void add(int i, int d) {
		sum[i / SQ] += d;
		cnt[i] += d;
		all += d;
	}
	int find_mx() {
		int id = n / SQ;
		int RB = id * SQ;
		for (int i = n;i >= RB;--i)
			if (cnt[i]) return i;
		for (int i = id - 1;i >= 0;--i)
			if (sum[i]) for (int j = (i * SQ) - 1;;--j)
				if (cnt[j]) return j;
		return -1;
	}
	int getsum(int l, int r) {
		assert(r == n);
		int res = all;
		--l;
		int lid = l / SQ;
		for (int i = 0;i < lid;++i) res -= sum[i];
		for (int i = lid * SQ;i <= l;++i) res -= cnt[i];
		return res;
	}
}RMQ[3];

int sum[MAX_N];
array<int, 3> getnxt() {
	int p = RMQ[1].find_mx();
	int v = RMQ[2].getsum(p + 1, m) & 1;
	DE(p, v);
	if (p != -1) {
		if (v == 1) return {-1, 1, 1};
		else return {-1, 2, 2};
	}
	if (v == 1) return {-1, 2, 1};
	else return {-1, 1, 2};
}
ll solveall() {
	sort(qry, qry + n);
	ll res = 0;

	RMQ[1].n = RMQ[2].n = m;

	auto addin = [&](int pos, int d) {
		int rp = lisan[pos].second;
		if (sum[pos]) RMQ[ sum[pos] ].add(rp, -1);
		sum[pos] += d;
		if (sum[pos]) RMQ[ sum[pos] ].add(rp, 1);

	};
	int cl = m, cr = m;

	for (int i = 0;i < n;++i) {
		auto [a, b, l, r] = qry[i];
		while (cl > l) addin(--cl, 1);
		while (cr > r) addin(--cr, 1);
		while (cr < r) addin(cr++,-1);
		while (cl < l) addin(cl++,-1);
		auto ret = getnxt();
		DE(ret[1], ret[2]);
		ll ans ;
		if (a <= b) ans = ret[1] == 1 ? min(a, b) : max(a, b);
		else ans = ret[2] == 1 ? min(a, b) : max(a, b);
		res += ans;
	}
	return res;
}
int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0;i < n;++i)
		cin >> a[i] >> b[i];
	for (int i = 0;i < m;++i) {
		cin >> mt[i];
		lisan[i] = {mt[i], i};
	}
	sort(lisan, lisan + m);
	for (int i = 0;i < n;++i) {
		int c = a[i], d = b[i];
		if (c > d) swap(c, d);
		c = lower_bound(lisan, lisan + m, make_pair(c, -1)) - lisan;
		d = lower_bound(lisan, lisan + m, make_pair(d, -1)) - lisan;
		qry[i] = {a[i], b[i], c, d};
	}
	cout << solveall() << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'std::array<int, 3> getnxt()':
fortune_telling2.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
fortune_telling2.cpp:67:2: note: in expansion of macro 'DE'
   67 |  DE(p, v);
      |  ^~
fortune_telling2.cpp: In function 'll solveall()':
fortune_telling2.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
fortune_telling2.cpp:97:3: note: in expansion of macro 'DE'
   97 |   DE(ret[1], ret[2]);
      |   ^~

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