Submission #584071

#	Time	Username	Problem	Language	Result	Execution time	Memory
584071		czhang2718	trapezoid (balkan11_trapezoid)	C++17	100 / 100	175 ms	17584 KiB

trapezoid

#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 / 100