oj.uz

답안 #235719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
235719 2020-05-29T13:30:25 Z luciocf 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 431 ms 34296 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 4e5+10;
const int mod = 30013;

struct Trapezio
{
	int a, b, c, d;
} t[maxn];

int dp_mx[maxn], dp_tot[maxn];

pii tree[4*maxn];

vector<int> st[maxn];

bool comp(Trapezio a, Trapezio b) {return a.d < b.d;}

void upd(int node, int l, int r, int pos, int x, int y)
{
	if (l == r)
	{
		if (x == tree[node].ff)
			tree[node] = {x, (y + tree[node].ss)%mod};

		if (x > tree[node].ff)
			tree[node] = {x, y};

		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, x, y);
	else upd(2*node+1, mid+1, r, pos, x, y);

	tree[node].ff = max(tree[2*node].ff, tree[2*node+1].ff);
	tree[node].ss = 0;

	if (tree[2*node].ff == tree[node].ff) tree[node].ss = (tree[node].ss + tree[2*node].ss)%mod;
	if (tree[2*node+1].ff == tree[node].ff) tree[node].ss = (tree[node].ss + tree[2*node+1].ss)%mod;
}

int query_mx(int node, int l, int r, int a, int b)
{
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return tree[node].ff;

	int mid = (l+r)>>1;

	return max(query_mx(2*node, l, mid, a, b), query_mx(2*node+1, mid+1, r, a, b));
}

int query_tot(int node, int l, int r, int a, int b, int mx)
{
	if (l > b || r < a) return 0;

	if (l >= a && r <= b)
	{
		if (tree[node].ff != mx) return 0;
		return tree[node].ss;
	}

	int mid = (l+r)>>1;

	return (query_tot(2*node, l, mid, a, b, mx) + query_tot(2*node+1, mid+1, r, a, b, mx))%mod;
}

void compress(int n)
{
	map<int, int> mp;

	for (int i = 1; i <= n; i++)
	{
		mp[t[i].a] = 0; mp[t[i].b] = 0;
		mp[t[i].c] = 0; mp[t[i].d] = 0;
	}

	int aux = 0;
	for (auto &x: mp)
		x.second = ++aux;

	for (int i = 1; i <= n; i++)
	{
		t[i].a = mp[t[i].a], t[i].b = mp[t[i].b];
		t[i].c = mp[t[i].c], t[i].d = mp[t[i].d];
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d %d %d %d", &t[i].a, &t[i].b, &t[i].c, &t[i].d);

	compress(n);

	sort(t+1, t+n+1, comp);

	for (int i = 1; i <= n; i++)
		st[t[i].c].push_back(i);

	upd(1, 1, maxn-1, maxn-1, 0, 1);
	dp_mx[n] = dp_tot[n] = 1;

	for (int i = n-1; i >= 1; i--)
	{
		for (int j = t[i+1].d; j > t[i].d; j--)
			for (auto ind: st[j])
				upd(1, 1, maxn-1, t[ind].a, dp_mx[ind], dp_tot[ind]);

		dp_mx[i] = 1 + query_mx(1, 1, maxn-1, t[i].b+1, maxn-1);
		dp_tot[i] = query_tot(1, 1, maxn-1, t[i].b+1, maxn-1, dp_mx[i]-1);
	}

	int mx = 0;
	for (int i = 1; i <= n; i++)
		mx = max(mx, dp_mx[i]);

	int tot = 0;
	for (int i = 1; i <= n; i++)
		if (dp_mx[i] == mx)
			tot = (tot + dp_tot[i])%mod;

	printf("%d %d\n", mx, tot);
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
trapezoid.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &t[i].a, &t[i].b, &t[i].c, &t[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9856 KB Output is correct
2 Correct 11 ms 9728 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Correct 14 ms 9984 KB Output is correct
5 Correct 15 ms 10496 KB Output is correct
6 Correct 18 ms 10496 KB Output is correct
7 Correct 21 ms 10624 KB Output is correct
8 Correct 24 ms 11008 KB Output is correct
9 Correct 39 ms 12664 KB Output is correct
10 Correct 57 ms 13048 KB Output is correct
11 Correct 88 ms 16504 KB Output is correct
12 Correct 195 ms 23672 KB Output is correct
13 Correct 253 ms 24824 KB Output is correct
14 Correct 303 ms 28408 KB Output is correct
15 Correct 355 ms 27512 KB Output is correct
16 Correct 408 ms 28664 KB Output is correct
17 Correct 399 ms 32504 KB Output is correct
18 Correct 244 ms 24184 KB Output is correct
19 Correct 365 ms 32460 KB Output is correct
20 Correct 431 ms 34296 KB Output is correct