Submission #531751

#	Time	Username	Problem	Language	Result	Execution time	Memory
531751		akhan42	Examination (JOI19_examination)	C++17	43 / 100	3091 ms	33928 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define at(m, k) (m.find(k) != m.end() ? m[k] : 0)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 100 * 1000 + 10;
int n, q;
int a[MX], b[MX], c[MX];
vi a2i[MX], b2i[MX];
int cl[MX];
int S = 250;


struct Fenw {
	int mx = MX - 1;
	vi bit;

	Fenw() {
		bit.assign(MX, 0);
	}

	void upd(int i, int v) {
		for(i += 1; i <= mx; i += i & (-i))
			bit[i] += v;
	}

	int psum(int i) {
		int sum = 0;
		for(; i > 0; i -= i & (-i))
			sum += bit[i];
		return sum;
	}

	int query(int cc) {
		return psum(mx) - psum(cc);
	}
};



bool cmp(pair<ii, ii> p1, pair<ii, ii> p2) {
	ii a = p1.F, b = p2.F;

	if(cl[a.F] != cl[b.F])
		return a.F < b.F;
	return (cl[a.F] % 2) ? a.S > b.S : a.S < b.S;
}


struct Mo {
	int l, r;
	Fenw fenw;

	void init(int l, int r) {
		this->l = l, this->r = r;

		forn(i, n)
			if(a[i] >= l && b[i] >= r)
				fenw.upd(c[i], 1);
	}

	void add_left() {
		l -= 1;
		for(int i: a2i[l])
			if(b[i] >= r)
				fenw.upd(c[i], 1);
			else
				break;
	}

	void pop_left() {
		for(int i: a2i[l])
			if(b[i] >= r)
				fenw.upd(c[i], -1);
			else
				break;
		l += 1;
	}

	void add_right() {
		for(int i: b2i[r])
			if(a[i] >= l)
				fenw.upd(c[i], -1);
			else
				break;
		r += 1;
	}

	void pop_right() {
		r -= 1;
		for(int i: b2i[r])
			if(a[i] >= l)
				fenw.upd(c[i], 1);
			else
				break;
	}

	int get_ans(int cc) {
		return fenw.query(cc);
	}
};


void comp(vi& v) {
	set<int> sl;
	for(int el: v)
		sl.insert(el);

	int ct = 0;
	map<int, int> v2i;
	for(int el: sl)
		v2i[el] = ct++;

	for(int& el: v)
		el = v2i[el];
}


bool cmp1(int i, int j) {
	return b[i] > b[j];
}


bool cmp2(int i, int j) {
	return a[i] > a[j];
}


void solve()
{
	cin >> n >> q;

	vi as, bs, cs;
	set<int> sas, sbs, scs;
	int mx_x = -1, mx_y = -1, mx_z = -1;
	forn(i, n) {
		int x, y;
		cin >> x >> y;

		as.pb(x);
		bs.pb(y);
		cs.pb(x + y);

		sas.insert(x);
		sbs.insert(y);
		scs.insert(x + y);

		maxeq(mx_x, x);
		maxeq(mx_y, y);
		maxeq(mx_z, x + y);
	}

	forn(_, q) {
		int l, r, cc;
		cin >> l >> r >> cc;

		if(sas.lower_bound(l) != sas.end())
			l = *sas.lower_bound(l);
		else
			l = mx_x + 1;

		if(sbs.lower_bound(r) != sbs.end())
			r = *sbs.lower_bound(r);
		else
			r = mx_y + 1;

		if(scs.lower_bound(cc) != scs.end())
			cc = *scs.lower_bound(cc);
		else
			cc = mx_z + 1;

		as.pb(l);
		bs.pb(r);
		cs.pb(cc);
	}

	comp(as);
	comp(bs);
	comp(cs);

	forn(i, n)
	{
		a[i] = as[i];
		b[i] = bs[i];
		c[i] = cs[i];

		a2i[a[i]].pb(i);
		b2i[b[i]].pb(i);
	}

	forn(i, MX) {
		sort(all(a2i[i]), cmp1);
		sort(all(b2i[i]), cmp2);
	}

	int ct = 0, i = 0;
	forn(l, MX) {
		if(sz(a2i[l]) > S || ct > S) {
			ct = sz(a2i[l]);
			i += 1;
		} else {
			ct += sz(a2i[l]);
		}
		cl[l] = i;
	}

	vector<pair<ii, ii>> qs;

	forn(ind, q) {
		int l = as[ind + n], r = bs[ind + n], cc = cs[ind + n];

		qs.pb({{l, r}, {cc, ind}});
	}

	sort(all(qs), cmp);

	Mo mo;
	vi ans(q);

	forn(i, q) {
		int l = qs[i].F.F, r = qs[i].F.S, cc = qs[i].S.F, ind = qs[i].S.S;

		if(i == 0) {
			mo.init(l, r);
		}
		else {
			while(l != mo.l || r != mo.r) {
				if(l < mo.l)
					mo.add_left();
				else if(r > mo.r)
					mo.add_right();
				else if(l > mo.l)
					mo.pop_left();
				else
					mo.pop_right();
			}
		}

		ans[ind] = mo.get_ans(cc);
//		cout << l << ' ' << r << ' ' << ans[ind] << '\n';
	}

	for(int el: ans)
		cout << el << '\n';
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("haybales.in", "r", stdin);
//	freopen("haybales.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--)
		solve();
}

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