oj.uz

답안 #106146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106146 2019-04-16T20:36:08 Z Kewo 사다리꼴 (balkan11_trapezoid) C++17
90 / 100
 500 ms 46328 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);
const int mod = (int)(30013);

int n, ans, tot;
ii tree[N << 2], dp[N];
set<int> s;
unordered_map<int, int> mp;
vector<ii> ev;

struct trap {
	int a, b, c, d;
	void read() {
		cin >> a >> b >> c >> d;
	}
	void compress() {
		a = mp[a];
		b = mp[b];
		c = mp[c];
		d = mp[d];
	}
}ar[N];

ii merge(ii x, ii y) {
	ii re;
	if(x.fi == y.fi)
		return {x.fi, (x.se + y.se) % mod};
	else
		return max(x, y);
}

void upd(int ind, int x, int y, int a, ii val) {
	if(a < x || y < a)
		return;
	if(x == y) {
		tree[ind] = val;
		return;
	}
	upd(left, x, mid, a, val);
	upd(right, mid + 1, y, a, val);
	tree[ind] = merge(tree[left], tree[right]);
}

ii get(int ind, int x, int y, int a, int b) {
	if(y < a || b < x)
		return {-1, 0};
	if(a <= x && y <= b)
		return tree[ind];
	return merge(get(left, x, mid, a, b), get(right, mid + 1, y, a, b));
}

int main() {
	fast_io();
	//freopen("inp.in", "r", stdin);
	
	cin >> n;
	for(int i = 1; i <= n; i++) {
		ar[i].read();
		s.insert(ar[i].a);
		s.insert(ar[i].b);
		s.insert(ar[i].c);
		s.insert(ar[i].d);
	}
	int t = 0;
	for(auto i : s)
		mp[i] = ++t;

	for(int i = 1; i <= n; i++)
		ar[i].compress();

	for(int i = 1; i <= n; i++) {
		ev.pb({i, 0});
		ev.pb({i, 1});
	}

	sort(ev.begin(), ev.end(), [&] (ii x, ii y) {
		int cmpx, cmpy;
		if(x.se == 0)
			cmpx = ar[x.fi].c;
		else
			cmpx = ar[x.fi].d;
		if(y.se == 0)
			cmpy = ar[y.fi].c;
		else
			cmpy = ar[y.fi].d;
		return cmpx < cmpy;
	});

	upd(1, 0, t, 0, {0, 1});

	for(auto i : ev) {
		int ind = i.fi;
		if(i.se == 0) {
			ii g = get(1, 0, t, 0, ar[ind].a - 1);
			dp[ind] = {g.fi + 1, g.se};
		}
		else
			upd(1, 0, t, ar[ind].b, dp[ind]);
		ans = max(ans, dp[ind].fi);
	}
	for(int i = 1; i <= n; i++)
		if(dp[i].fi == ans) {
			tot += dp[i].se;
			tot %= mod;
		}
	cout << ans << spc << tot;
}

Subtask #1
90.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 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 7 ms 1408 KB Output is correct
6 Correct 10 ms 1792 KB Output is correct
7 Correct 11 ms 1536 KB Output is correct
8 Correct 21 ms 2432 KB Output is correct
9 Correct 53 ms 5508 KB Output is correct
10 Correct 54 ms 6436 KB Output is correct
11 Correct 131 ms 12392 KB Output is correct
12 Correct 253 ms 25272 KB Output is correct
13 Correct 304 ms 27012 KB Output is correct
14 Correct 424 ms 37892 KB Output is correct
15 Correct 397 ms 33284 KB Output is correct
16 Correct 472 ms 34692 KB Output is correct
17 Execution timed out 533 ms 43456 KB Time limit exceeded
18 Correct 319 ms 27164 KB Output is correct
19 Correct 472 ms 43464 KB Output is correct
20 Execution timed out 537 ms 46328 KB Time limit exceeded