oj.uz

Submission #584071

# Submission time Handle Problem Language Result Execution time Memory
584071 2022-06-26T18:46:06 Z czhang2718 trapezoid (balkan11_trapezoid) C++17
100 / 100
 175 ms 17584 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second
const int MOD=30013;

const int N=1e5;
int n;
pii seg[8*N];

pii comb(pii a, pii b){
	if(a.f==b.f) return {a.f, (b.s+a.s)%MOD};
	return max(a,b);
}

pii query(int x, int lx, int rx, int r){
	if(lx>=r) return {0,0};
	if(rx<=r) return seg[x];
	int m=(lx+rx)/2;
	pii a=query(2*x+1, lx, m, r);
	pii b=query(2*x+2, m, rx, r);
	return comb(a,b);
}

void upd(int i, pii p, int x=0, int lx=0, int rx=2*n){
	if(rx-lx==1){
		seg[x]=p;
		return;
	}
	int m=(lx+rx)/2;
	if(i<m) upd(i, p, 2*x+1, lx, m);
	else upd(i, p, 2*x+2, m, rx);
	seg[x]=comb(seg[2*x+1], seg[2*x+2]);
}

struct tr{
	int ul, ur, dl, dr;
};

tr T[N];
pii ans[N];
map<int, int> mp;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> n;
	
	vector<int> xs;
	vector<int> cc;
	for(int i=0; i<n; i++){
		cin >> T[i].ul >> T[i].ur >> T[i].dl >> T[i].dr;
		cc.push_back(T[i].ul);
		cc.push_back(T[i].ur);
		mp[T[i].dl]=mp[T[i].dr]=i;
		xs.push_back(T[i].dl);
		xs.push_back(T[i].dr);
	}
	
	sort(xs.begin(), xs.end());
	sort(cc.begin(), cc.end());
	
	for(int i=0; i<n; i++){
		T[i].ul=lower_bound(cc.begin(), cc.end(), T[i].ul)-cc.begin();
		T[i].ur=lower_bound(cc.begin(), cc.end(), T[i].ur)-cc.begin();
	}
	
	for(int x:xs){
		int i=mp[x];
		if(x==T[i].dl){
			ans[i]=query(0, 0, 2*n, T[i].ul);
			ans[i].f++;
			ans[i].s=max(ans[i].s, 1);
		}
		else{
			upd(T[i].ur, ans[i]);
		}
	}
	
	pii p=query(0, 0, 2*n, 2*n);
	cout << p.f << " " << p.s; 
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 8 ms 1236 KB Output is correct
9 Correct 17 ms 2092 KB Output is correct
10 Correct 34 ms 3924 KB Output is correct
11 Correct 49 ms 4680 KB Output is correct
12 Correct 84 ms 9004 KB Output is correct
13 Correct 101 ms 10364 KB Output is correct
14 Correct 129 ms 13748 KB Output is correct
15 Correct 144 ms 14420 KB Output is correct
16 Correct 153 ms 14928 KB Output is correct
17 Correct 155 ms 15724 KB Output is correct
18 Correct 152 ms 16308 KB Output is correct
19 Correct 172 ms 16452 KB Output is correct
20 Correct 175 ms 17584 KB Output is correct