oj.uz

Submission #97757

# Submission time Handle Problem Language Result Execution time Memory
97757 2019-02-18T10:23:23 Z Anai trapezoid (balkan11_trapezoid) C++14
0 / 100
 500 ms 412 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() {
	freopen("trapezoid.in", "r", stdin);
	freopen("trapezoid.out", "w", stdout);
	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 'int main()':
trapezoid.cpp:84:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("trapezoid.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:85:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("trapezoid.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 256 KB Time limit exceeded
2 Execution timed out 1063 ms 256 KB Time limit exceeded
3 Execution timed out 1060 ms 256 KB Time limit exceeded
4 Execution timed out 1063 ms 256 KB Time limit exceeded
5 Execution timed out 1077 ms 256 KB Time limit exceeded
6 Execution timed out 1034 ms 384 KB Time limit exceeded
7 Execution timed out 1026 ms 412 KB Time limit exceeded
8 Execution timed out 1064 ms 256 KB Time limit exceeded
9 Execution timed out 1004 ms 256 KB Time limit exceeded
10 Execution timed out 1058 ms 256 KB Time limit exceeded
11 Execution timed out 1073 ms 256 KB Time limit exceeded
12 Execution timed out 1079 ms 256 KB Time limit exceeded
13 Execution timed out 1065 ms 256 KB Time limit exceeded
14 Execution timed out 1071 ms 256 KB Time limit exceeded
15 Execution timed out 1069 ms 384 KB Time limit exceeded
16 Execution timed out 1074 ms 256 KB Time limit exceeded
17 Execution timed out 1025 ms 256 KB Time limit exceeded
18 Execution timed out 1070 ms 384 KB Time limit exceeded
19 Execution timed out 1014 ms 256 KB Time limit exceeded
20 Execution timed out 1043 ms 356 KB Time limit exceeded