Submission #379253

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
379253	2021-03-17T15:47:57 Z	Cantfindme	trapezoid (balkan11_trapezoid)	C++17	100 / 100	335 ms	43024 KB

trapezoid

#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

#	Verdict	Execution time	Memory	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