oj.uz

Submission #535809

# Submission time Handle Problem Language Result Execution time Memory
535809 2022-03-11T10:21:36 Z new_acc trapezoid (balkan11_trapezoid) C++14
65 / 100
 108 ms 5448 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<<17;
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;
	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
65.0 / 100.0

# Verdict Execution time Memory 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 4 ms 596 KB Output is correct
8 Correct 5 ms 592 KB Output is correct
9 Correct 10 ms 980 KB Output is correct
10 Correct 15 ms 1584 KB Output is correct
11 Correct 23 ms 1876 KB Output is correct
12 Correct 46 ms 3416 KB Output is correct
13 Correct 55 ms 4000 KB Output is correct
14 Incorrect 66 ms 4496 KB Output isn't correct
15 Incorrect 79 ms 4684 KB Output isn't correct
16 Incorrect 77 ms 4756 KB Output isn't correct
17 Incorrect 76 ms 4904 KB Output isn't correct
18 Incorrect 66 ms 5116 KB Output isn't correct
19 Incorrect 91 ms 5140 KB Output isn't correct
20 Incorrect 108 ms 5448 KB Output isn't correct