Submission #339626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339626	2020-12-25T18:30:17 Z	mosiashvililuka	trapezoid (balkan11_trapezoid)	C++14	100 / 100	188 ms	18028 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	3 ms	748 KB	Output is correct
6	Correct	4 ms	876 KB	Output is correct
7	Correct	6 ms	1132 KB	Output is correct
8	Correct	8 ms	1260 KB	Output is correct
9	Correct	20 ms	2156 KB	Output is correct
10	Correct	35 ms	3948 KB	Output is correct
11	Correct	40 ms	4716 KB	Output is correct
12	Correct	95 ms	9196 KB	Output is correct
13	Correct	112 ms	10988 KB	Output is correct
14	Correct	126 ms	12908 KB	Output is correct
15	Correct	149 ms	13492 KB	Output is correct
16	Correct	163 ms	14484 KB	Output is correct
17	Correct	162 ms	15340 KB	Output is correct
18	Correct	160 ms	16268 KB	Output is correct
19	Correct	163 ms	17132 KB	Output is correct
20	Correct	188 ms	18028 KB	Output is correct