oj.uz

Submission #106286

# Submission time Handle Problem Language Result Execution time Memory
106286 2019-04-17T19:09:02 Z hugo_pm Examination (JOI19_examination) C++17
100 / 100
 2001 ms 798092 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 783308 KB Output is correct
2 Correct 594 ms 783136 KB Output is correct
3 Correct 609 ms 783224 KB Output is correct
4 Correct 579 ms 783104 KB Output is correct
5 Correct 568 ms 783196 KB Output is correct
6 Correct 587 ms 783352 KB Output is correct
7 Correct 612 ms 783336 KB Output is correct
8 Correct 599 ms 783480 KB Output is correct
9 Correct 592 ms 783300 KB Output is correct
10 Correct 616 ms 783284 KB Output is correct
11 Correct 589 ms 783204 KB Output is correct
12 Correct 586 ms 783204 KB Output is correct
13 Correct 630 ms 783284 KB Output is correct
14 Correct 647 ms 783352 KB Output is correct
15 Correct 627 ms 783364 KB Output is correct
16 Correct 565 ms 783340 KB Output is correct
17 Correct 567 ms 783224 KB Output is correct
18 Correct 581 ms 783148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 795504 KB Output is correct
2 Correct 1228 ms 795616 KB Output is correct
3 Correct 1141 ms 795620 KB Output is correct
4 Correct 808 ms 795048 KB Output is correct
5 Correct 999 ms 794876 KB Output is correct
6 Correct 826 ms 794172 KB Output is correct
7 Correct 1092 ms 795512 KB Output is correct
8 Correct 1101 ms 795504 KB Output is correct
9 Correct 1133 ms 795640 KB Output is correct
10 Correct 910 ms 794716 KB Output is correct
11 Correct 843 ms 794808 KB Output is correct
12 Correct 823 ms 793868 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 795504 KB Output is correct
2 Correct 1228 ms 795616 KB Output is correct
3 Correct 1141 ms 795620 KB Output is correct
4 Correct 808 ms 795048 KB Output is correct
5 Correct 999 ms 794876 KB Output is correct
6 Correct 826 ms 794172 KB Output is correct
7 Correct 1092 ms 795512 KB Output is correct
8 Correct 1101 ms 795504 KB Output is correct
9 Correct 1133 ms 795640 KB Output is correct
10 Correct 910 ms 794716 KB Output is correct
11 Correct 843 ms 794808 KB Output is correct
12 Correct 823 ms 793868 KB Output is correct
13 Correct 1366 ms 796040 KB Output is correct
14 Correct 1411 ms 796052 KB Output is correct
15 Correct 1214 ms 795544 KB Output is correct
16 Correct 908 ms 795260 KB Output is correct
17 Correct 1163 ms 795272 KB Output is correct
18 Correct 853 ms 794124 KB Output is correct
19 Correct 1288 ms 796028 KB Output is correct
20 Correct 1262 ms 796036 KB Output is correct
21 Correct 1330 ms 796024 KB Output is correct
22 Correct 897 ms 794704 KB Output is correct
23 Correct 798 ms 794744 KB Output is correct
24 Correct 1006 ms 793808 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 783308 KB Output is correct
2 Correct 594 ms 783136 KB Output is correct
3 Correct 609 ms 783224 KB Output is correct
4 Correct 579 ms 783104 KB Output is correct
5 Correct 568 ms 783196 KB Output is correct
6 Correct 587 ms 783352 KB Output is correct
7 Correct 612 ms 783336 KB Output is correct
8 Correct 599 ms 783480 KB Output is correct
9 Correct 592 ms 783300 KB Output is correct
10 Correct 616 ms 783284 KB Output is correct
11 Correct 589 ms 783204 KB Output is correct
12 Correct 586 ms 783204 KB Output is correct
13 Correct 630 ms 783284 KB Output is correct
14 Correct 647 ms 783352 KB Output is correct
15 Correct 627 ms 783364 KB Output is correct
16 Correct 565 ms 783340 KB Output is correct
17 Correct 567 ms 783224 KB Output is correct
18 Correct 581 ms 783148 KB Output is correct
19 Correct 1223 ms 795504 KB Output is correct
20 Correct 1228 ms 795616 KB Output is correct
21 Correct 1141 ms 795620 KB Output is correct
22 Correct 808 ms 795048 KB Output is correct
23 Correct 999 ms 794876 KB Output is correct
24 Correct 826 ms 794172 KB Output is correct
25 Correct 1092 ms 795512 KB Output is correct
26 Correct 1101 ms 795504 KB Output is correct
27 Correct 1133 ms 795640 KB Output is correct
28 Correct 910 ms 794716 KB Output is correct
29 Correct 843 ms 794808 KB Output is correct
30 Correct 823 ms 793868 KB Output is correct
31 Correct 1366 ms 796040 KB Output is correct
32 Correct 1411 ms 796052 KB Output is correct
33 Correct 1214 ms 795544 KB Output is correct
34 Correct 908 ms 795260 KB Output is correct
35 Correct 1163 ms 795272 KB Output is correct
36 Correct 853 ms 794124 KB Output is correct
37 Correct 1288 ms 796028 KB Output is correct
38 Correct 1262 ms 796036 KB Output is correct
39 Correct 1330 ms 796024 KB Output is correct
40 Correct 897 ms 794704 KB Output is correct
41 Correct 798 ms 794744 KB Output is correct
42 Correct 1006 ms 793808 KB Output is correct
43 Correct 1907 ms 798004 KB Output is correct
44 Correct 1937 ms 798092 KB Output is correct
45 Correct 1892 ms 798028 KB Output is correct
46 Correct 978 ms 796420 KB Output is correct
47 Correct 1560 ms 796556 KB Output is correct
48 Correct 876 ms 794096 KB Output is correct
49 Correct 1883 ms 797852 KB Output is correct
50 Correct 2001 ms 797908 KB Output is correct
51 Correct 1856 ms 797800 KB Output is correct
52 Correct 1433 ms 796424 KB Output is correct
53 Correct 842 ms 795512 KB Output is correct