oj.uz

답안 #97759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97759 2019-02-18T10:23:47 Z Anai 사다리꼴 (balkan11_trapezoid) C++14
85 / 100
 500 ms 29020 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fi cin
#define fo cout
 
using pii = pair<int, int>;
 
const int N = 1e5 + 5, MOD = 30013;
 
struct Point {
	int idx, x, y;
	bool cap; };
 
pii dp[N], pom[N * 16];
 
vector<Point> pts;
pii qval;
int n, bnd, ql, qr, qpos;
 
static int fix(int arg) {
	return arg >= MOD ? arg - MOD : arg; }
 
static pii join(const pii &a, const pii &b) {
	if (a.first > b.first)
		return a;
	if (a.first < b.first)
		return b;
	return pii(a.first, fix(a.second + b.second)); }
 
static pii query(int nod, int st, int dr) {
	if (ql <= st && dr <= qr)
		return pom[nod];
	int mid = (st + dr) / 2;
	pii l = (ql <= mid ? query(2 * nod, st, mid) : pii(0, 0));
	pii r = (mid < qr ? query(2 * nod + 1, mid + 1, dr) : pii(0, 0));
	return join(l, r); }
 
static void update(int nod, int st, int dr) {
	if (st == dr) {
		pom[nod] = (pom[nod].first == qval.first ? pii(qval.first, qval.second + pom[nod].second) : qval);
		pom[nod].second = fix(pom[nod].second);
		return; }
	int mid = (st + dr) / 2;
	if (qpos <= mid)
		update(2 * nod, st, mid);
	else
		update(2 * nod + 1, mid + 1, dr);
	pom[nod] = join(pom[2 * nod], pom[2 * nod + 1]); }
 
static void normalize() {
	map<int, int> mp;
	int idx = 0;
	for (auto i: pts)
		mp[i.x] = mp[i.y] = 0;
	for (auto &i: mp)
		i.second = ++idx;
	for (auto &i: pts) {
		i.x = mp[i.x];
		i.y = mp[i.y]; }
	bnd = mp.size(); }
 
static char nextch() {
	const int BMAX = 1 << 17;
	static char buff[BMAX];
	static int bp = BMAX;
	if (bp == BMAX) {
		fread(buff, 1, BMAX, stdin);
		bp = 0; }
	return buff[bp++]; }
 
static void get(int &x) {
	char ch;
	do {
		ch = nextch(); }
	while (ch < '0' || '9' < ch);
	x = 0;
	do {
		x = x * 10 + (ch - '0');
		ch = nextch(); }
	while ('0' <= ch && ch <= '9'); }
 
int main() {
	int crd, cnt;
 
	get(n);
	pts.reserve(n);
	for (int i = 0; i < n; ++i) {
		int a, b, c, d;
		get(a), get(b), get(c), get(d);
		pts.push_back({i, a, c, 1});
		pts.push_back({i, b, d, 0}); }
 
	normalize();
	sort(begin(pts), end(pts), [&](const Point &a, const Point &b) {
		return pii(a.x, a.y) < pii(b.x, b.y); });
 
	for (const auto &i: pts) {
		if (i.cap) {
			ql = 1, qr = i.y;
			dp[i.idx] = query(1, 1, bnd);
			if (++dp[i.idx].first == 1)
				dp[i.idx].second = 1;}
		else {
			qpos = i.y;
			qval = dp[i.idx];
			update(1, 1, bnd); } }
 
	crd = cnt = 0;
	for (int i = 0; i < n; ++i)
		crd = max(crd, dp[i].first);
	for (int i = 0; i < n; ++i)
		if (dp[i].first == crd)
			cnt = fix(cnt + dp[i].second);
 
	printf("%d %d\n", crd, cnt);
 
	return 0; }

Compilation message

trapezoid.cpp: In function 'char nextch()':
trapezoid.cpp:68:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fread(buff, 1, BMAX, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
85.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 10 ms 1408 KB Output is correct
7 Correct 9 ms 1152 KB Output is correct
8 Correct 16 ms 1536 KB Output is correct
9 Correct 30 ms 3416 KB Output is correct
10 Correct 58 ms 4676 KB Output is correct
11 Correct 101 ms 8172 KB Output is correct
12 Correct 256 ms 15768 KB Output is correct
13 Correct 354 ms 18508 KB Output is correct
14 Correct 410 ms 24736 KB Output is correct
15 Correct 421 ms 19692 KB Output is correct
16 Execution timed out 502 ms 21348 KB Time limit exceeded
17 Execution timed out 535 ms 28236 KB Time limit exceeded
18 Correct 214 ms 18424 KB Output is correct
19 Correct 445 ms 27684 KB Output is correct
20 Execution timed out 572 ms 29020 KB Time limit exceeded