oj.uz

Submission #1039386

# Submission time Handle Problem Language Result Execution time Memory
1039386 2024-07-30T19:39:06 Z 1L1YA trapezoid (balkan11_trapezoid) C++17
46 / 100
 109 ms 35012 KB 
//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=1e5+11;
const int lg=23;

int n,m,a[N],b[N],c[N],d[N];
pii dp[N],fen[N<<2];
vector<int> vc1[N<<2],vc2[N<<2];

void upd(int x,pii y){
	for(;x<=m;x+=x&-x)
		if(y.F>fen[x].F)	fen[x]=y;
		else if(y.F==fen[x].F)	fen[x].S+=y.S;
}

pii get(int x){
	pii ans={0,1};
	for(;x;x-=x&-x)
		if(fen[x].F>ans.F)	ans=fen[x];
		else if(fen[x].F==ans.F)	ans.S+=fen[x].S;
	return ans;
}

int main(){
	FastIO

	cin >> n;
	vector<int> comp;
	for(int i=1;i<=n;i++){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		comp.Pb(a[i]);comp.Pb(b[i]);comp.Pb(c[i]);comp.Pb(d[i]);
	}
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	m=SZ(comp);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(all(comp),a[i])-comp.begin()+1;
		b[i]=lower_bound(all(comp),b[i])-comp.begin()+1;
		c[i]=lower_bound(all(comp),c[i])-comp.begin()+1;
		d[i]=lower_bound(all(comp),d[i])-comp.begin()+1;
		vc1[a[i]].Pb(i);
		vc2[b[i]].Pb(i);
	}
	for(int i=1;i<=m;i++)	fen[i]={0,0};
	for(int i=1;i<=m;i++){
		for(int j: vc1[i])	dp[j]=get(c[j]-1),dp[j].F++;
		for(int j: vc2[i])	upd(d[j],dp[j]);
	}
	cout << get(m).F << sep << get(m).S << endl;

	return 0;
}

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Partially correct 4 ms 23132 KB Partially correct
4 Partially correct 4 ms 23224 KB Partially correct
5 Partially correct 5 ms 23388 KB Partially correct
6 Partially correct 6 ms 23388 KB Partially correct
7 Partially correct 6 ms 23484 KB Partially correct
8 Partially correct 8 ms 23640 KB Partially correct
9 Partially correct 12 ms 24288 KB Partially correct
10 Partially correct 20 ms 25476 KB Partially correct
11 Partially correct 28 ms 25996 KB Partially correct
12 Partially correct 55 ms 29132 KB Partially correct
13 Partially correct 66 ms 30156 KB Partially correct
14 Partially correct 90 ms 31512 KB Partially correct
15 Partially correct 82 ms 32036 KB Partially correct
16 Partially correct 91 ms 32712 KB Partially correct
17 Partially correct 97 ms 33228 KB Partially correct
18 Partially correct 84 ms 33912 KB Partially correct
19 Partially correct 104 ms 34500 KB Partially correct
20 Partially correct 109 ms 35012 KB Partially correct