제출 #929438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
929438		horiseun	Examination (JOI19_examination)	C++17	100 / 100	327 ms	17052 KiB

examination

#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <array>
#include <random>
#include <climits>
#include <cassert>
#include <algorithm>
using namespace std;

template<typename A, typename B> ostream& operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator << (ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) { os << sep << x, sep = ", "; } return os << '}'; }
void D_out() { cerr << endl; }
template<typename Head, typename... Tail> void D_out(Head H, Tail... T) { cerr << ' ' << H; D_out(T...); }

#ifdef DEBUG
	#define D(...) cerr << '(' << #__VA_ARGS__ << "):", D_out(__VA_ARGS__)
#else
	#define D(...)
#endif

//#define int long long
#define ll long long
#define ld long double
#define f first
#define s second
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
#define lowbit(x) (x & (-x))

const ll MOD = 1e9 + 7;
const ll INF = 1e18;

struct Event {
	int a, b, c, idx;

	Event (): a(0), b(0), c(0), idx(0) {}
	Event (int ta, int tb, int tc, int tidx): a(ta), b(tb), c(tc), idx(tidx) {}
}; 

struct BIT {
	int bit[200005];
	vector<int> nodes;
	
	void update(int x, int v) {
		nodes.push_back(x);
		for (; x; x -= lowbit(x)) {
			bit[x] += v;
		}
	}

	int query(int x) {
		int ret = 0;
		for (; x < 200005; x += lowbit(x)) {
			ret += bit[x];
		}
		return ret;
	}

	void reset() {
		for (int x : nodes) {
			for (; x; x -= lowbit(x)) {
				bit[x] = 0;
			}
		}
		nodes.clear();
	}
};

int n, q, sz, ans[100005];
Event events[200005];
vector<int> coordx, coordy, coordz;
BIT bt;

void cdq(int l, int r) {
	if (l == r) return;
	int m = (l + r) / 2;
	cdq(l, m);
	cdq(m + 1, r);
	for (int lidx = l, ridx = m; lidx <= m; lidx++) {
		while (ridx < r && events[lidx].b <= events[ridx + 1].b) {
			ridx++;
			if (!events[ridx].idx) {
				bt.update(events[ridx].c, 1);	
			}
		}
		if (events[lidx].idx) {
			ans[events[lidx].idx] += bt.query(events[lidx].c);
		}
	}
	bt.reset();
	inplace_merge(events + l, events + m + 1, events + r + 1, [&] (Event lft, Event rht) {
		return lft.b > rht.b;
	});
}

void solve() {
	cin >> n >> q;
	for (int i = 0, s, t; i < n; i++) {
		cin >> s >> t;
		events[sz++] = Event(s, t, s + t, 0);
		coordx.push_back(s);
		coordy.push_back(t);
		coordz.push_back(s + t);
	}
	for (int i = 1, x, y, z; i <= q; i++) {
		cin >> x >> y >> z;
		events[sz++] = Event(x, y, z, i);
		coordx.push_back(x);
		coordy.push_back(y);
		coordz.push_back(z);
	}
	sort(all(coordx));
	sort(all(coordy));
	sort(all(coordz));
	coordx.erase(unique(all(coordx)), coordx.end());
	coordy.erase(unique(all(coordy)), coordy.end());
	coordz.erase(unique(all(coordz)), coordz.end());
	for (int i = 0; i < sz; i++) {
		events[i].a = lower_bound(all(coordx), events[i].a) - coordx.begin() + 1;
		events[i].b = lower_bound(all(coordy), events[i].b) - coordy.begin() + 1;
		events[i].c = lower_bound(all(coordz), events[i].c) - coordz.begin() + 1;
	}
	sort(events, events + sz, [&] (Event lft, Event rht) {
		if (lft.a != rht.a) return lft.a < rht.a;
		else if (lft.b != rht.b) return lft.b < rht.b;
		else if (lft.c != rht.c) return lft.c < rht.c;
		return lft.idx > rht.idx;
	});
	cdq(0, sz - 1);
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	

	int t = 1; //cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		//cout << "Case #" << tc << ": ";
		solve();
	}
}

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