Submission #375093

#	Time	Username	Problem	Language	Result	Execution time	Memory
375093		Kevin_Zhang_TW	Examination (JOI19_examination)	C++17	100 / 100	340 ms	13384 KiB

examination

#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 

struct lisan : vector<int> {
	void done() { sort(AI()), erase(unique(AI()), end()); }
	int operator()(int i) { return lower_bound(AI(), i) - begin(); }
};

const int MAX_N = 100010, MAX_M = MAX_N << 1, MAX_C = MAX_M;
int n, q;
int res[MAX_N];

const int QT = 0, MT = 1, LT = 1, RT = 0;

// big one comes first
struct info {
	int a, b, c, tp, id, sd;
	tuple<int,int,int,int,int> gtp() {
		return make_tuple(a, b, c, sd, tp);
	}
	info (int a, int b, int c, int tp, int id = -1, int sd = -1) :
		a(a), b(b), c(c), tp(tp), id(id), sd(sd) {}
	info () :
		a(0), b(0), c(0), tp(0), id(0), sd(0) {}
} arr[MAX_M] ;
bool operator < (info a, info b) {
	return a.gtp() > b.gtp();
}

struct rbit {
	int n;
	vector<int> val;
	rbit(int _n) : n(_n + 10) {
		val.resize(n);
	}
	void add(int i, int d) {
		for (;i;i ^= i&-i) 
			val[i] += d;
	}
	int qry(int i) {
		int res = 0;
		for (;i < n;i += i&-i)
			res += val[i];
		return res;
	}
};

rbit tree(0);

void solve(int l, int r) {

//	for (int i = l;i < r;++i)
//		for (int j = l;j < i;++j) 
//			if (arr[j].b >= arr[i].b  &&
//				arr[j].c >= arr[i].c) {
//				if (arr[j].tp == MT && arr[i].tp == QT) {
//					++res[ arr[i].id ];
//				}
//			}
//
//	return;
					
	if (r-l <= 1) return;
	int mid = l + r >> 1;
	solve(l, mid), solve(mid, r);

	for (int i = l;i < mid;++i) {
		auto &[a, b, c, tp, id, sd] = arr[i];
		sd = LT;
	}
	for (int i = mid;i < r;++i) {
		auto &[a, b, c, tp, id, sd] = arr[i];
		sd = RT;
	}

	DE(l, mid, r);

	auto cmp = [&](info x, info y) {
		auto [a, b, c, tp, id, sd] = x;
		auto [aa, bb, cc, tpp, idd, sdd] = y;
		return make_tuple(b, c, tp, sd) > 
			make_tuple(bb, cc, tpp, sdd);
	};
	inplace_merge(arr+l, arr+mid, arr+r, cmp);

	for (int i = l;i < r;++i) {
		auto &[a, b, c, tp, id, sd] = arr[i];
		DE(a, b, c, tp, id, sd);

		if (sd == LT && tp == MT)
			tree.add(c, 1);
		
		if (sd == RT && tp == QT) {
			DE(a, b, c, tp, id, sd);
			//DE(tree.qry(c));
			res[id] += tree.qry(c);
		}

	}
	for (int i = l;i < r;++i) {
		auto &[a, b, c, tp, id, sd] = arr[i];

		if (sd == LT && tp == MT)
			tree.add(c, -1);

	}

}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	for (int i = 0;i < n;++i) {
		int a, b;
		cin >> a >> b;
		arr[i] = {a, b, a + b, MT};
	}
	for (int i = 0;i < q;++i) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[i + n] = {a, b, c, QT, i};
	}

	sort(arr, arr + n + q);

	{
		lisan L; L.reserve(n + q);
		for (int i = 0;i < n + q;++i) {
			auto [a, b, c, tp, id, sd] = arr[i];
			L.pb(c);
		}
		L.done();
		for (int i = 0;i < n + q;++i) {
			auto &[a, b, c, tp, id, sd] = arr[i];
			c = L(c) + 1;
		}
	}

	tree = rbit(n + q + 10);

	solve(0, n + q);

	for (int i = 0;i < q;++i)
		cout << res[i] << '\n';
}

Compilation message (stderr)

examination.cpp: In function 'void solve(int, int)':
examination.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int mid = l + r >> 1;
      |            ~~^~~
examination.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
examination.cpp:90:2: note: in expansion of macro 'DE'
   90 |  DE(l, mid, r);
      |  ^~
examination.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
examination.cpp:102:3: note: in expansion of macro 'DE'
  102 |   DE(a, b, c, tp, id, sd);
      |   ^~
examination.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
examination.cpp:108:4: note: in expansion of macro 'DE'
  108 |    DE(a, b, c, tp, id, sd);
      |    ^~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57