Submission #1220848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220848		LM1	trapezoid (balkan11_trapezoid)	C++20	100 / 100	341 ms	44280 KiB

trapezoid

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
#define Tree int h,int l,int r
#define Left h*2,l,(l+r)/2
#define Right h*2+1,(l+r)/2+1,r
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,T,mod=30013;
int a[N],b[N],c[N],d[N];
vector<int>U[4*N],G[4*N];
//struct node{
//	int x;
//	int c;
//};
pii v[16*N],dp[N],bs;
void compress(){
	vector<int>s;
	map<int,int>f;
	for(int i=1;i<=n;++i){
		s.pb(a[i]),s.pb(b[i]);
		s.pb(c[i]),s.pb(d[i]);
	}
	sort(s.begin(),s.end());
	s.erase(unique(s.begin(),s.end()),s.end());
	T=s.size();
	for(int i=0;i<s.size();++i){
		f[s[i]]=i+1;
	}
	for(int i=1;i<=n;++i){
		a[i]=f[a[i]];
		b[i]=f[b[i]];
		c[i]=f[c[i]];
		d[i]=f[d[i]];
	}
}
pii comb(pii a,pii b){
	pii d;
	d.ff=max(a.ff,b.ff),d.ss=0;
	if(d.ff==a.ff)d.ss=(d.ss+a.ss)%mod;
	if(d.ff==b.ff)d.ss=(d.ss+b.ss)%mod;
	return d;
}
void upd(Tree,int id,pii vl){
	if(id<l or r<id)return;
	if(id==l and id==r){
		if(v[h].ff==vl.ff)v[h].ss=(v[h].ss+vl.ss)%mod;
		else v[h]=vl;		
		return;
	}
	upd(Left,id,vl);
	upd(Right,id,vl);
	v[h]=comb(v[h*2],v[h*2+1]);
}
pii get(Tree,int L,int R){
	if(r<L or R<l)return bs;
	if(L<=l and r<=R)return v[h];
	return comb(get(Left,L,R),get(Right,L,R));
}
main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n;
	bs.ss=bs.ff=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}
	compress();
	for(int i=1;i<=n;i++){
		U[b[i]].pb(i);
		G[a[i]].pb(i);
	}
	for(int i=1;i<=T;i++){
		for(int j=0;j<G[i].size();++j){
			int id=G[i][j];
			pii res=get(1,1,T,1,c[id]-1);
			if(!res.ss)res.ss=1;
			res.ff++;
			dp[id]=res;
		}
		for(int j=0;j<U[i].size();j++){
			int id=U[i][j];
			upd(1,1,T,d[id],dp[id]);
		}		
	}
	cout<<v[1].ff<<" "<<v[1].ss<<"\n";
}

Compilation message (stderr)

trapezoid.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

• Subtask 1: 100 / 100