Submission #106286

#	Time	Username	Problem	Language	Result	Execution time	Memory
106286		hugo_pm	Examination (JOI19_examination)	C++17	100 / 100	2001 ms	798092 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne2 = (1LL << 40LL);

struct Node
{
	int val;
	pii itv;
	Node *lc=nullptr, *rc=nullptr;
	Node* left();
	Node* right();

	void init()
	{
		val=0;
		itv = {0, borne2-1};
		lc=nullptr;
		rc=nullptr;
	}
	int requete(int a, int b)
	{
		if (itv.fi > b || itv.se < a) return 0;
		if (a <= itv.fi && itv.se <= b) return val;
		return left()->requete(a,b) + right()->requete(a,b);
	}
	void incr(int x)
	{
		if (itv.fi > x || itv.se < x) return;
		if (itv.fi == x && itv.se == x) { ++val; return; }
		left()->incr(x);
		right()->incr(x);
		val = left()->val + right()->val;
	}
};

const int MAX_BUF = 1000*1000*1000 / 50;
Node buf[MAX_BUF];
int lsBuf = 0;

Node* Node::left()
{
	if (lc == nullptr) {
		lc = &buf[lsBuf++];
		lc->val = 0;
		lc->itv = {itv.fi, (itv.fi+itv.se)/2LL};
	}
	return lc;
}
Node* Node::right()
{
	if (rc == nullptr) {
		rc = &buf[lsBuf++];
		rc->val = 0;
		rc->itv = {(itv.fi+itv.se)/2LL + 1LL, itv.se};
	}
	return rc;
}

struct Requete
{
	int maths=0, info=0, rqAdd=0, tot=0, rep=0, ind=0;
};

bool cmpAdd(Requete a, Requete b)
{
	return tie(a.rqAdd, a.ind) < tie(b.rqAdd, b.ind);

}
bool cmpMaths(Requete a, Requete b)
{
	return tie(a.maths, a.ind) < tie(b.maths, b.ind);
}

bool cmpInd(Requete a, Requete b)
{
	return a.ind < b.ind;
}

const int borne = 4 * ((int)(1e5) + 5);
pii etud[borne];
Requete req[borne];
int nbEtud, nbReq;
Node* sc;
Node* oth;



void bourrin()
{
	form(i, nbEtud) cin >> etud[i].fi >> etud[i].se;

	form(iReq, nbReq) {
		int crMaths, crInfo, crTot;
		cin >> crMaths >> crInfo >> crTot;
		int rep = 0;
		form(indEtud, nbEtud) {
			auto &ed = etud[indEtud];
			if (ed.fi >= crMaths && ed.se >= crInfo && ed.fi + ed.se >= crTot) {
				++rep;
			}
		}
		cout << rep << "\n";
	}
}
void solve()
{
	cin >> nbEtud >> nbReq;
	if (nbEtud <= 3000 && nbReq <= 3000) { bourrin(); return; }
	form(i, nbEtud) cin >> etud[i].fi >> etud[i].se;
	sort(etud, etud+nbEtud);

	form(i, nbReq) {
		cin >> req[i].maths >> req[i].info >> req[i].tot;
		req[i].rqAdd = req[i].tot - req[i].info;
		req[i].ind = i;
	}

	sort(req, req+nbReq, cmpAdd);

	vector<int> tmp(borne, 0);
	sc = &buf[lsBuf++];
	oth = &buf[lsBuf++];
	sc->init();
	oth->init();

	int iAdd = nbEtud-1;

	ford(iReq, nbReq) {
		auto &cur = req[iReq];
		while (iAdd >= 0 && etud[iAdd].fi >= cur.rqAdd) {
			int ol = etud[iAdd].se;
			sc->incr(ol);

			int ol2 = etud[iAdd].se + etud[iAdd].fi;
			oth->incr(ol2);

			--iAdd;
		}
		cur.rep = sc->requete(cur.info, borne2-1);
		int lim = cur.tot;
		chmin(lim, borne2-1);
		chmax(lim, 0LL);
		cur.rep -= oth->requete(lim, borne2-1);
	}

	sc = &buf[lsBuf++];
	oth = &buf[lsBuf++];
	sc->init();
	oth->init();
	sort(req, req+nbReq, cmpMaths);

	iAdd=nbEtud-1;

	ford(iReq, nbReq) {
		auto &cur = req[iReq];
		while (iAdd >= 0 && etud[iAdd].fi >= cur.maths) {
			int ol = etud[iAdd].se;
			sc->incr(ol);

			int ol2 = etud[iAdd].se + etud[iAdd].fi;
			oth->incr(ol2);

			--iAdd;
		}
		if (cur.maths + cur.info >= cur.tot) {
			cur.rep = sc->requete(cur.info, borne2-1);
			continue;
		}
		int lim = cur.tot;
		chmin(lim, borne2-1);
		chmax(lim, 0LL);
		cur.rep += oth->requete(lim, borne2-1);
	}

	sort(req, req+nbReq, cmpInd);
	form(iReq, nbReq) {
		cout << req[iReq].rep << "\n";
	}
}

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