oj.uz

답안 #328981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328981 2020-11-18T16:38:52 Z kshitij_sodani 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 143 ms 15688 KB 
//#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.0 / 100.0

# 결과 실행 시간 메모리 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 5 ms 1004 KB Output is correct
8 Correct 8 ms 1260 KB Output is correct
9 Correct 13 ms 2020 KB Output is correct
10 Correct 24 ms 3548 KB Output is correct
11 Correct 34 ms 4316 KB Output is correct
12 Correct 71 ms 8148 KB Output is correct
13 Correct 84 ms 9556 KB Output is correct
14 Correct 99 ms 11208 KB Output is correct
15 Correct 113 ms 11848 KB Output is correct
16 Correct 117 ms 12616 KB Output is correct
17 Correct 124 ms 13512 KB Output is correct
18 Correct 111 ms 14152 KB Output is correct
19 Correct 129 ms 14920 KB Output is correct
20 Correct 143 ms 15688 KB Output is correct