oj.uz

답안 #379253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379253 2021-03-17T15:47:57 Z Cantfindme 사다리꼴 (balkan11_trapezoid) C++17
100 / 100
 335 ms 43024 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 30013;

int n;
struct trap {
	int a,b, c, d;
};

trap A[maxn];
vector <pii> v;
vector <int> pp;

struct node {
	int s,m,e;
	int maxv;
	int ways;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e;
		m = (s+e)/2;
		maxv = ways = 0;
		
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}				
	}
	
	void up(int x, int vv) {
		if (s == e) {
			maxv = vv;
			return;
		} 
		if (x > m) r -> up(x,vv);
		else l -> up(x,vv);
		maxv = max(l -> maxv, r -> maxv);
	}
	
	int rmq(int x, int y) {
		if (s == x and e == y) return maxv;
		else if (x > m) return r -> rmq(x,y);
		else if (y <= m) return l -> rmq(x,y);
		else return max(l -> rmq(x,m), r -> rmq(m+1,y));
	}
	
	void up2(int x, int vv) {
		if (s == e) {
			ways = vv;
			return;
		}
		if (x > m) r -> up2(x,vv);
		else l -> up2(x,vv);
		ways = (l -> ways + r -> ways) % mod;
	}
	
	int sum(int x, int y) {
		if (s == x and e == y) return ways;
		else if (x > m) return r -> sum(x,y);
		else if (y <= m) return l -> sum(x,y);
		else return (l -> sum(x,m) + r -> sum(m+1,y)) % mod;
	}
}*root;

vector <int> vec2[maxn];
int mp[maxn];
int waysans[maxn];

int32_t main() {
	FAST
	cin >> n;
	for (int i =0;i<n;i++) {
		int a,b,c,d; cin >> a >> b >> c >> d;
		A[i] = {a,b,c,d};
		v.push_back(pii(a,pi(0,i)));
		v.push_back(pii(b,pi(1,i)));
		pp.push_back(c);
		pp.push_back(d);
	}
	pp.push_back(0);
	
	sort(all(pp));
	pp.resize(unique(all(pp)) - pp.begin());
	
	sort(all(v));
	root = new node(0,pp.size()+1);
	
	for (auto [x, cur] : v) {
		auto [type, indx] = cur;
		if (type == 0) {
			int lb = lower_bound(all(pp), A[indx].c) - pp.begin();
			
			int best = root -> rmq(0, lb);
			mp[indx] = best + 1;	
			vec2[mp[indx]].push_back(indx);		
		} else {
			int lb = lower_bound(all(pp), A[indx].d) - pp.begin();
			
			root -> up(lb, mp[indx]);
		}
	}
	
	int ans = root -> rmq(0, pp.size());
	root -> up2(0, 1);
	
	for (int i = 1;i<=ans;i++) {
		vector <pii> vv;
		
		for (auto indx: vec2[i-1]) {
			vv.push_back(pii(A[indx].b, pi(0,indx)));
		}
		
		for (auto indx: vec2[i]) {
			vv.push_back(pii(A[indx].a, pi(1,indx)));
		}
		
		sort(all(vv));
		
		for (auto [x, cur] : vv) {
			auto [type, indx] = cur;
			if (type == 0) {
				int lb = lower_bound(all(pp), A[indx].d) - pp.begin();
				root -> up2(lb, waysans[indx]);
			} else {
				int lb = lower_bound(all(pp), A[indx].c) - pp.begin();
				int total = root -> sum(0,lb);
				waysans[indx] = total;
			}
		}
		
		for (auto indx: vec2[i-1]) {
			int lb = lower_bound(all(pp), A[indx].d) - pp.begin();
			root -> up2(lb, 0);
		}
		
		if (i == 1)  {
			root -> up2(0, 0);
		}
	}
	
	int rans = 0;
	for (auto indx: vec2[ans]) {
		rans += waysans[indx];
		rans %= mod;
	}
	cout << ans << " " << rans;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 3 ms 2924 KB Output is correct
4 Correct 4 ms 3052 KB Output is correct
5 Correct 7 ms 3564 KB Output is correct
6 Correct 9 ms 3948 KB Output is correct
7 Correct 13 ms 4480 KB Output is correct
8 Correct 15 ms 4904 KB Output is correct
9 Correct 28 ms 6820 KB Output is correct
10 Correct 50 ms 10784 KB Output is correct
11 Correct 72 ms 12832 KB Output is correct
12 Correct 157 ms 22812 KB Output is correct
13 Correct 189 ms 26908 KB Output is correct
14 Correct 217 ms 30992 KB Output is correct
15 Correct 265 ms 33040 KB Output is correct
16 Correct 283 ms 35216 KB Output is correct
17 Correct 308 ms 37136 KB Output is correct
18 Correct 233 ms 38800 KB Output is correct
19 Correct 294 ms 40976 KB Output is correct
20 Correct 335 ms 43024 KB Output is correct