Submission #535808

#	Time	Username	Problem	Language	Result	Execution time	Memory
535808		new_acc	trapezoid (balkan11_trapezoid)	C++14	38 / 100	90 ms	8052 KiB

trapezoid

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<17;
const int mod=30013;
struct st{
	int a,b,ind;
};
st t[N*2];
pair<int,int>seg[(SS<<1)+10];
pair<int,int>dp[N];
void upd(int ind,pair<int,int> x){
	seg[ind+=SS]=x;
	for(ind>>=1;ind>0;ind>>=1){
		int maxi=max(seg[ind<<1].fi,seg[(ind<<1)+1].fi);
		seg[ind].fi=maxi,seg[ind].se=0;
		if(seg[(ind<<1)].fi==maxi) seg[ind].se+=seg[ind<<1].se;
		if(seg[(ind<<1)+1].fi==maxi) seg[ind].se+=seg[(ind<<1)+1].se;
	}
}
pair<int,int> Query(int a,int b){
	pair<int,int> res={0,0};
	for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
		if(!(a&1)){
			if(seg[a+1].fi==res.fi) res.se+=seg[a+1].se;
			if(seg[a+1].fi>res.fi) res=seg[a+1];
		}
		if(b&1){
			if(seg[b-1].fi==res.fi) res.se+=seg[b-1].se;
			if(seg[b-1].fi>res.fi) res=seg[b-1];
		}
	}
	return res;
}
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		t[(i<<1)-1]={a,c,i},t[i<<1]={b,d,-i};
	}
	int curr=0,pom=0;
	sort(t+1,t+1+(n<<1),[](st a,st b){
		return a.b<b.b;
	});
	for(int i=1;i<=(n<<1);i++){
		if(i==1 or t[i].b!=pom) curr++;
		pom=t[i].b;
		t[i].b=curr;
	}
	sort(t+1,t+1+(n<<1),[](st a,st b){
		return a.a<b.a;
	});
	for(int i=1;i<=(n<<1);i++){
		vector<st> akt;
		int p=t[i].a;
		while(t[i].a==p) akt.push_back(t[i]),i++;
		i--;
		for(auto u:akt){
			if(u.ind>0){
				dp[u.ind]=Query(1,u.b);
				dp[u.ind].fi++,dp[u.ind].se=max(1,dp[u.ind].se);
			}
		}
		for(auto u:akt)
			if(u.ind<0) upd(u.b,dp[-u.ind]);
	}
	int maxi=0,res=0;
	for(int i=1;i<=n;i++) maxi=max(maxi,dp[i].fi);
	for(int i=1;i<=n;i++) if(dp[i].fi==maxi) (res+=dp[i].se)%=mod;
	cout<<maxi<<" "<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

• Subtask 1: 38 / 100