제출 #364365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364365		Kevin_Zhang_TW	운세 보기 2 (JOI14_fortune_telling2)	C++17	35 / 100	3048 ms	10604 KiB

fortune_telling2

#undef KEV
#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 = 450;

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 node {
	int nxt[3];
	node (int val = 0) {
		if (val == 0) {
			nxt[1] = 1;
			nxt[2] = 2;
		}
		if (val == 1) {
			nxt[1] = 2;
			nxt[2] = 2;
		}
		if (val == 2) {
			nxt[1] = 2;
			nxt[2] = 1;
		}
	}
	node (node a, node b) {
		for (int i = 1;i <= 2;++i) 
			nxt[i] = b.nxt[ a.nxt[i] ];
	}
};
struct sgt {
	vector<node> v;
	int n;
	sgt (int _n) : n(_n) {
		v.resize(n<<1);
	}
	void modi(int i, int val) {
		i += n;
		v[i] = node(val);
		for (;i>>=1;) 
			update(i);
	}
	void update(int i) {
		v[i] = node(v[i<<1], v[i<<1|1]);
	}
	node qry(int l, int r) {
		l += n, r += n;
		node lres(0), rres(0);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) lres = node(lres, v[l++]);
			if (r&1) rres = node(v[--r], rres);
		}
		return node(lres, rres);
	}
};

int sum[MAX_N];

int brute(int a, int b) {
	for (int i = 0;i < m;++i)
		if (a <= mt[i]) swap(a, b);
	return a;
}
ll solveall() {
	sort(qry, qry + n);
	ll res = 0;

	sgt tree(m);

	auto addin = [&](int pos, int d) {
		sum[pos] += d;
		tree.modi(lisan[pos].second, sum[pos]);
	};

	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 = tree.qry(0, m);

		ll ans ;
		if (a <= b) ans = ret.nxt[1] == 1 ? min(a, b) : max(a, b);
		else ans = ret.nxt[2] == 1 ? min(a, b) : max(a, b);

		DE(a, b, ans, brute(a, b));
		debug(sum, sum + m);
		DE(ret.nxt[1], ret.nxt[2]);

		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';
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'll solveall()':
fortune_telling2.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define DE(...) 0
      |                 ^
fortune_telling2.cpp:115:3: note: in expansion of macro 'DE'
  115 |   DE(a, b, ans, brute(a, b));
      |   ^~
fortune_telling2.cpp:17:20: warning: statement has no effect [-Wunused-value]
   17 | #define debug(...) 0
      |                    ^
fortune_telling2.cpp:116:3: note: in expansion of macro 'debug'
  116 |   debug(sum, sum + m);
      |   ^~~~~
fortune_telling2.cpp:16:17: warning: statement has no effect [-Wunused-value]
   16 | #define DE(...) 0
      |                 ^
fortune_telling2.cpp:117:3: note: in expansion of macro 'DE'
  117 |   DE(ret.nxt[1], ret.nxt[2]);
      |   ^~

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