oj.uz

Submission #380430

# Submission time Handle Problem Language Result Execution time Memory
380430 2021-03-21T18:29:15 Z ritul_kr_singh trapezoid (balkan11_trapezoid) C++17
100 / 100
 182 ms 17772 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
#define arr array<int, 5>

const int MOD = 30013;


pair<int, int> f(pair<int, int> x, pair<int, int> y){
	if(x.first==y.first) return {x.first, (x.second + y.second) % MOD};
	else return max(x, y);
}

struct segtree{
	int sz = 1;
	const pair<int, int> ID = {0, 0};
	vector<pair<int, int>> a;
	segtree(int n){
		while(sz < n) sz *= 2;
		a.assign(2*sz, ID);
	}
	void update(int i, pair<int, int> val, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = val);
		int mx = (lx+rx)/2;
		if(i<mx) update(i, val, 2*x+1, lx, mx);
		else update(i, val, 2*x+2, mx, rx);
		a[x] = f(a[2*x+1], a[2*x+2]);
	}
	void update(int i, pair<int, int> val){ update(i, val, 0, 0, sz); }
	pair<int, int> get(int r, int x, int lx, int rx){
		if(lx>=r) return ID;
		if(rx<=r) return a[x];
		int mx = (lx+rx)/2;
		return f(get(r, 2*x+1, lx, mx), get(r, 2*x+2, mx, rx));
	}
	pair<int, int> get(int r){ return get(r+1, 0, 0, sz); }
};

bool comp1(arr x, arr y){ return x[1] < y[1]; }
bool comp3(arr x, arr y){ return x[3] < y[3]; }

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n; cin >> n;
	array<int, 4> a[n];
	for(int i=0; i<n; ++i) cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
	sort(a, a+n);
	
	arr by1[n], by3[n];
	for(int i=0; i<n; ++i){
		for(int j=0; j<4; ++j) by1[i][j] = by3[i][j] = a[i][j];
		by1[i][4] = by3[i][4] = i;
	}
	sort(by1, by1+n, comp1);
	sort(by3, by3+n, comp3);

	int posBy3[n];
	pair<int, int> ans[n];

	for(int i=0; i<n; ++i) posBy3[by3[i][4]] = i, ans[i] = {1, 1};

	int ind = 0;
	segtree st(n);

	pair<int, int> final = {0, 0};

	for(int i=0; i<n; ++i){
		while(ind<n and by1[ind][1] < a[i][0]){
			int k = by1[ind][4];
			int l = posBy3[k];
			st.update(l, ans[k]);
			++ind;
		}
		if(a[i][2] < by3[0][3]) continue;
		int low = 0, high = n-1;
		while(low<high){
			int mid = (low+high)/2;
			if(by3[mid+1][3] < a[i][2]) low = mid+1;
			else high = mid;
		}
		pair<int, int> res = st.get(low);
		if(res.first){
			ans[i] = {res.first + 1, res.second};
		}
		final = f(final, ans[i]);
	}
	cout << final.first sp final.second;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 876 KB Output is correct
7 Correct 5 ms 1004 KB Output is correct
8 Correct 7 ms 1260 KB Output is correct
9 Correct 16 ms 2156 KB Output is correct
10 Correct 29 ms 3948 KB Output is correct
11 Correct 39 ms 4716 KB Output is correct
12 Correct 85 ms 9068 KB Output is correct
13 Correct 115 ms 10348 KB Output is correct
14 Correct 127 ms 13804 KB Output is correct
15 Correct 143 ms 14444 KB Output is correct
16 Correct 150 ms 15084 KB Output is correct
17 Correct 168 ms 15776 KB Output is correct
18 Correct 143 ms 16364 KB Output is correct
19 Correct 164 ms 17132 KB Output is correct
20 Correct 182 ms 17772 KB Output is correct