Submission #535811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535811	2022-03-11T10:23:48 Z	new_acc	trapezoid (balkan11_trapezoid)	C++14	100 / 100	99 ms	6476 KB

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<<18;
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){
	ind+=SS;
	if(seg[ind].fi==x.fi) (seg[ind].se+=x.se)%=mod;
	else{
		if(seg[ind].fi>x.fi) return;
		seg[ind]=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)%=mod;
		if(seg[(ind<<1)+1].fi==maxi) (seg[ind].se+=seg[(ind<<1)+1].se)%=mod;
	}
}
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)%=mod;
			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)%=mod;
			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;
	});
	upd(0,{0,1});
	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(0,u.b);
				dp[u.ind].fi++;
			}
		}
		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

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	340 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	3 ms	468 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	5 ms	596 KB	Output is correct
9	Correct	9 ms	980 KB	Output is correct
10	Correct	16 ms	1576 KB	Output is correct
11	Correct	23 ms	1876 KB	Output is correct
12	Correct	49 ms	3404 KB	Output is correct
13	Correct	55 ms	4128 KB	Output is correct
14	Correct	79 ms	4684 KB	Output is correct
15	Correct	73 ms	4992 KB	Output is correct
16	Correct	79 ms	5268 KB	Output is correct
17	Correct	80 ms	5640 KB	Output is correct
18	Correct	66 ms	5896 KB	Output is correct
19	Correct	85 ms	5836 KB	Output is correct
20	Correct	99 ms	6476 KB	Output is correct