Submission #328981

#	Time	Username	Problem	Language	Result	Execution time	Memory
328981		kshitij_sodani	사다리꼴 (balkan11_trapezoid)	C++14	100 / 100	143 ms	15688 KiB

trapezoid

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int n;

int ind[100001][2];
int mod=30013;
pair<int,int> dp[100001];
pair<int,int> re(pair<int,int> aa,pair<int,int> bb){
	if(aa.a>bb.a){
		return aa;
	}
	if(aa.a<bb.a){
		return bb;
	}
	return {aa.a,(aa.b+bb.b)%mod};
}
pair<int,int> tree[100001*8];
void update(int no,int l,int r,int i,pair<int,int> val){
	if(l==r){
		tree[no]=val;
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i,val);
		}
		else{
			update(no*2+2,mid+1,r,i,val);
		}
		tree[no]=re(tree[no*2+1],tree[no*2+2]);
	}
}
pair<int,int> query(int no,int l,int r,int aa,int bb){
	if(aa>bb or l>bb or r<aa){
		return {0,0};
	}
	if(aa<=l and r<=bb){
		//cout<<l<<"//"<<r<<","<<tree[no].a<<","<<tree[no].b<<endl;
		return tree[no];
	}
	int mid=(l+r)/2;
	return re(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	vector<pair<int,pair<int,int>>> ss;
	vector<pair<int,pair<int,int>>> tt;
	for(int i=0;i<n;i++){
		int aa,bb,cc,dd;
		cin>>aa>>bb>>cc>>dd;
		ss.pb({aa,{i,0}});
		ss.pb({bb,{i,1}});
		tt.pb({cc,{i,0}});
		tt.pb({dd,{i,1}});
	}
	for(int i=0;i<8*n;i++){
		tree[i]={0,0};
	}
	sort(ss.begin(),ss.end());
	for(int i=0;i<2*n;i++){
		ind[ss[i].b.a][ss[i].b.b]=i;
	}
	sort(tt.begin(),tt.end());
	pair<int,int> ma={0,0};
	for(auto j:tt){
		if(j.b.b==0){
		//	cout<<ind[j.b.a][0]-1<<endl;
			pair<int,int> xx=query(0,0,2*n-1,0,ind[j.b.a][0]-1);
			xx.a+=1;
		//	cout<<endl;
			if(xx.b==0){
				xx.b=1;
			}
			dp[j.b.a]=xx;
			ma=re(ma,dp[j.b.a]);
		//	cout<<j.b.a<<":"<<xx.a<<":"<<xx.b<<endl;
		}
		else{
			update(0,0,2*n-1,ind[j.b.a][1],dp[j.b.a]);
			//cout<<ind[j.b.a][1]<<",,,"<<j.b.a<<endl;
		}
		
	}
	cout<<ma.a<<" "<<ma.b<<endl;













 
 
	return 0;
}

• Subtask 1: 100 / 100