oj.uz

Submission #535808

# Submission time Handle Problem Language Result Execution time Memory
535808 2022-03-11T10:16:18 Z new_acc trapezoid (balkan11_trapezoid) C++14
38 / 100
 90 ms 8052 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){
	seg[ind+=SS]=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;
		if(seg[(ind<<1)+1].fi==maxi) seg[ind].se+=seg[(ind<<1)+1].se;
	}
}
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;
			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;
			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;
	});
	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(1,u.b);
				dp[u.ind].fi++,dp[u.ind].se=max(1,dp[u.ind].se);
			}
		}
		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
38.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 340 KB Partially correct
5 Correct 3 ms 436 KB Output is correct
6 Partially correct 3 ms 540 KB Partially correct
7 Partially correct 3 ms 724 KB Partially correct
8 Correct 5 ms 724 KB Output is correct
9 Partially correct 9 ms 1236 KB Partially correct
10 Partially correct 14 ms 2092 KB Partially correct
11 Partially correct 20 ms 2508 KB Partially correct
12 Partially correct 44 ms 4828 KB Partially correct
13 Partially correct 55 ms 5700 KB Partially correct
14 Incorrect 61 ms 6420 KB Output isn't correct
15 Incorrect 69 ms 6684 KB Output isn't correct
16 Incorrect 76 ms 6900 KB Output isn't correct
17 Incorrect 76 ms 7288 KB Output isn't correct
18 Incorrect 63 ms 7488 KB Output isn't correct
19 Incorrect 82 ms 7608 KB Output isn't correct
20 Incorrect 90 ms 8052 KB Output isn't correct