Submission #1157333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157333		Zflop	trapezoid (balkan11_trapezoid)	C++20	24 / 100	282 ms	32344 KiB

trapezoid

#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() {
	cin >> N;
	vector<int>normalizare;
	map<int,int>m;
	for (int i = 1; i <= N;++i) {
		cin >> A[i] >> B[i] >> C[i] >> D[i]; 
		normalizare.push_back(A[i]);
		normalizare.push_back(B[i]);
		normalizare.push_back(C[i]);
		normalizare.push_back(D[i]);
		}
	sort(normalizare.begin(),normalizare.end());
	for (int i = 0; i < (int)normalizare.size();++i)
		m[normalizare[i]] = i + 1;
	
	for (int i = 1; i <= N;++i) {
		puncte.push_back({m[B[i]],m[D[i]],0,i});
		puncte.push_back({m[A[i]],m[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 maxim = 0;
	for (int i = 1; i <= N;++i)
		maxim = max(maxim,ans[i]);
	cout << maxim << ' ' << 1 << '\n';
	}

main() {
	solve();
}

Compilation message (stderr)

trapezoid.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main() {
      | ^~~~

• Subtask 1: 24 / 100