Submission #339626

#	Time	Username	Problem	Language	Result	Execution time	Memory
339626		mosiashvililuka	trapezoid (balkan11_trapezoid)	C++14	100 / 100	188 ms	18028 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,mod=30013,ppi,dp[100009],z,x,dp2[100009],pas1,pas2;
pair <pair <int, int>, pair <int, int> > p[100009];
pair <int, int> pp[200009];
pair <int, int> fen[200009];
map <int, int> m;
map <int, int>::iterator it;
void upd(int q, int w, int ww){
	while(q<=200000){
		if(fen[q].first<w){
			fen[q].first=w;
			fen[q].second=ww;
		}else{
			if(fen[q].first==w){
				fen[q].second+=ww;
				fen[q].second%=mod;
			}
		}
		q=q+(q&(-q));
	}
}
void read(int q){
	z=0;x=1;
	while(q>=1){
		if(fen[q].first>z){
			z=fen[q].first;
			x=fen[q].second;
		}else{
			if(fen[q].first==z){
				x+=fen[q].second;
				x%=mod;
			}
		}
		q=q-(q&(-q));
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++){
		cin>>p[i].first.first>>p[i].first.second>>p[i].second.first>>p[i].second.second;
		m[p[i].second.first]=1;
		m[p[i].second.second]=1;
		ppi++;
		pp[ppi].first=p[i].first.first;
		pp[ppi].second=i;
		ppi++;
		pp[ppi].first=p[i].first.second;
		pp[ppi].second=i;
	}
	zx=0;
	for(it=m.begin(); it!=m.end(); it++){
		zx++;
		m[(*it).first]=zx;
	}
	for(i=1; i<=a; i++){
		p[i].second.first=m[p[i].second.first];
		p[i].second.second=m[p[i].second.second];
	}
	sort(pp+1,pp+ppi+1);
	for(ii=1; ii<=ppi; ii++){
		i=pp[ii].second;c=pp[ii].first;
		if(p[pp[ii].second].first.first==pp[ii].first){
			read(p[i].second.first);
			z++;
			dp[i]=z;dp2[i]=x;
			if(pas1<z){
				pas1=z;pas2=x;
			}else{
				if(pas1==z){
					pas2+=x;
					pas2%=mod;
				}
			}
		}else{
			upd(p[i].second.second,dp[i],dp2[i]);
		}
	}
	cout<<pas1<<" "<<pas2;
	return 0;
}

• Subtask 1: 100 / 100