oj.uz

Submission #380428

# Submission time Handle Problem Language Result Execution time Memory
380428 2021-03-21T18:25:21 Z ritul_kr_singh trapezoid (balkan11_trapezoid) C++17
43 / 100
 182 ms 20460 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;

struct segtree{
	int sz = 1;
	const pair<int, int> ID = {0, 0};
	vector<pair<int, int>> a;
	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);
	}
	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 = max(final, ans[i]);
	}
	cout << final.first sp final.second;
}

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 364 KB Partially correct
4 Partially correct 2 ms 492 KB Partially correct
5 Partially correct 3 ms 748 KB Partially correct
6 Partially correct 4 ms 876 KB Partially correct
7 Partially correct 7 ms 1280 KB Partially correct
8 Partially correct 9 ms 1388 KB Partially correct
9 Partially correct 16 ms 2412 KB Partially correct
10 Partially correct 31 ms 4608 KB Partially correct
11 Partially correct 43 ms 5356 KB Partially correct
12 Partially correct 89 ms 10348 KB Partially correct
13 Correct 105 ms 11884 KB Output is correct
14 Partially correct 131 ms 15724 KB Partially correct
15 Partially correct 148 ms 16364 KB Partially correct
16 Partially correct 153 ms 17280 KB Partially correct
17 Partially correct 159 ms 18028 KB Partially correct
18 Partially correct 142 ms 18796 KB Partially correct
19 Partially correct 169 ms 19692 KB Partially correct
20 Partially correct 182 ms 20460 KB Partially correct