oj.uz

답안 #535811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535811 2022-03-11T10:23:48 Z new_acc 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 99 ms 6476 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<18;
const int mod=30013;
struct st{
	int a,b,ind;
};
st t[N*2];
pair<int,int>seg[(SS<<1)+10];
pair<int,int>dp[N];
void upd(int ind,pair<int,int> x){
	ind+=SS;
	if(seg[ind].fi==x.fi) (seg[ind].se+=x.se)%=mod;
	else{
		if(seg[ind].fi>x.fi) return;
		seg[ind]=x;
	}
	for(ind>>=1;ind>0;ind>>=1){
		int maxi=max(seg[ind<<1].fi,seg[(ind<<1)+1].fi);
		seg[ind].fi=maxi,seg[ind].se=0;
		if(seg[(ind<<1)].fi==maxi) (seg[ind].se+=seg[ind<<1].se)%=mod;
		if(seg[(ind<<1)+1].fi==maxi) (seg[ind].se+=seg[(ind<<1)+1].se)%=mod;
	}
}
pair<int,int> Query(int a,int b){
	pair<int,int> res={0,0};
	for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
		if(!(a&1)){
			if(seg[a+1].fi==res.fi) (res.se+=seg[a+1].se)%=mod;
			if(seg[a+1].fi>res.fi) res=seg[a+1];
		}
		if(b&1){
			if(seg[b-1].fi==res.fi) (res.se+=seg[b-1].se)%=mod;
			if(seg[b-1].fi>res.fi) res=seg[b-1];
		}
	}
	return res;
}
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		t[(i<<1)-1]={a,c,i},t[i<<1]={b,d,-i};
	}
	int curr=0,pom=0;
	sort(t+1,t+1+(n<<1),[](st a,st b){
		return a.b<b.b;
	});
	for(int i=1;i<=(n<<1);i++){
		if(i==1 or t[i].b!=pom) curr++;
		pom=t[i].b;
		t[i].b=curr;
	}
	sort(t+1,t+1+(n<<1),[](st a,st b){
		return a.a<b.a;
	});
	upd(0,{0,1});
	for(int i=1;i<=(n<<1);i++){
		vector<st> akt;
		int p=t[i].a;
		while(t[i].a==p) akt.push_back(t[i]),i++;
		i--;
		for(auto u:akt){
			if(u.ind>0){
				dp[u.ind]=Query(0,u.b);
				dp[u.ind].fi++;
			}
		}
		for(auto u:akt)
			if(u.ind<0) upd(u.b,dp[-u.ind]);
	}
	int maxi=0,res=0;
	for(int i=1;i<=n;i++) maxi=max(maxi,dp[i].fi);
	for(int i=1;i<=n;i++) if(dp[i].fi==maxi) (res+=dp[i].se)%=mod;
	cout<<maxi<<" "<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 9 ms 980 KB Output is correct
10 Correct 16 ms 1576 KB Output is correct
11 Correct 23 ms 1876 KB Output is correct
12 Correct 49 ms 3404 KB Output is correct
13 Correct 55 ms 4128 KB Output is correct
14 Correct 79 ms 4684 KB Output is correct
15 Correct 73 ms 4992 KB Output is correct
16 Correct 79 ms 5268 KB Output is correct
17 Correct 80 ms 5640 KB Output is correct
18 Correct 66 ms 5896 KB Output is correct
19 Correct 85 ms 5836 KB Output is correct
20 Correct 99 ms 6476 KB Output is correct