Submission #1157328

#TimeUsernameProblemLanguageResultExecution timeMemory
1157328Zfloptrapezoid (balkan11_trapezoid)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
ifstream in("trapezoid.in");
ofstream out("trapezoid.out");
const int NMAX = (int)1e5 * 2;
int N,A[NMAX],B[NMAX],C[NMAX],D[NMAX],ans[NMAX],mx[NMAX * 4];
vector<vector<int>>puncte;
int get_max(int a,int b,int l,int r,int x) {
	if (a <= l && r <= b)
		return mx[x];
	if (r < a || b < l)
		return 0;
	int mid = (l + r) / 2;
	return max(get_max(a,b,l,mid,2 * x),get_max(a,b,mid + 1,r,2 * x + 1));
	} 
void set_max(int i,int v,int l,int r,int x) {
	if (l == r) {
		mx[x] = v;
		return;
		}
	int mid = (l + r) / 2;
	if (i <= mid)
		set_max(i,v,l,mid,2 * x);
	else
		set_max(i,v,mid + 1,r,2 * x + 1);
	mx[x] = max(mx[2 * x],mx[2 * x + 1]);
	}

void solve() {
	in >> N;
	for (int i = 1; i <= N;++i) {
		in >> A[i] >> B[i] >> C[i] >> D[i]; 
		puncte.push_back({B[i],D[i],0,i});
		puncte.push_back({A[i],C[i],1,i});
		}
	sort(puncte.begin(),puncte.end());
	reverse(puncte.begin(),puncte.end());
	for (auto& v : puncte) {
		if (v[2] == 0) {
			ans[v[3]] = get_max(v[1],NMAX - 1,1,NMAX,1) + 1;
			}
		else {
			set_max(v[1],ans[v[3]],1,NMAX,1);
			}
		}
	int m = 0;
	for (int i = 1; i <= N;++i)
		m = max(m,ans[i]);
	out << m << ' ' << 1 << '\n';
	}

main() {
	solve();
}

Compilation message (stderr)

trapezoid.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...