제출 #1157338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157338		Zflop	사다리꼴 (balkan11_trapezoid)	C++20	100 / 100	318 ms	38076 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
ifstream in("trapezoid.in");
ofstream out("trapezoid.out");
const int NMAX = (int)1e5 * 2;
const int MOD = 30013;
int N,A[NMAX],B[NMAX],C[NMAX],D[NMAX],ans[NMAX],mx[NMAX * 4],ways[NMAX * 4],dp[NMAX];
vector<vector<int>>puncte;
pair<int,int>get_max(int a,int b,int l,int r,int x) {
	if (a <= l && r <= b)
		return {mx[x],ways[x]};
	if (r < a || b < l)
		return {0,0};
	int mid = (l + r) / 2;
	pair<int,int>left = get_max(a,b,l,mid,2 * x);
	pair<int,int>right = get_max(a,b,mid + 1,r,2 * x + 1);
	if (left.first < right.first)
		return right;
	if (right.first < left.first)
		return left;
	return {left.first,(left.second + right.second) % MOD};
	} 
void set_max(int i,int v,int w,int l,int r,int x) {
	if (l == r) {
		mx[x] = v;
		ways[x] = w;
		return;
		}
	int mid = (l + r) / 2;
	if (i <= mid)
		set_max(i,v,w,l,mid,2 * x);
	else
		set_max(i,v,w,mid + 1,r,2 * x + 1);
	if (mx[2 * x] < mx[2 * x + 1]) {
		mx[x] = mx[2 * x + 1];
		ways[x] = ways[2 * x + 1];
		}
	else if (mx[2 * x] > mx[2 * x + 1]) {
		mx[x] = mx[2 * x];
		ways[x] = ways[2 * x];
		}
	else {
		mx[x] = mx[2 * x];
		ways[x] = (ways[2 * x] + ways[2 * x + 1]) % MOD;
		}
	}

void solve() {
	cin >> N;
	vector<int>normalizare1,normalizare2;
	map<int,int>m1,m2;
	for (int i = 1; i <= N;++i) {
		cin >> A[i] >> B[i] >> C[i] >> D[i]; 
		normalizare1.push_back(A[i]);
		normalizare1.push_back(B[i]);
		normalizare2.push_back(C[i]);
		normalizare2.push_back(D[i]);
		}
	sort(normalizare1.begin(),normalizare1.end());
	sort(normalizare2.begin(),normalizare2.end());
	for (int i = 0; i < (int)normalizare1.size();++i) {
		m1[normalizare1[i]] = i + 1;
		m2[normalizare2[i]] = i + 1;
		}
	
	for (int i = 1; i <= N;++i) {
		puncte.push_back({m1[B[i]],m2[D[i]],0,i});
		puncte.push_back({m1[A[i]],m2[C[i]],1,i});
		}
	sort(puncte.begin(),puncte.end());
	reverse(puncte.begin(),puncte.end());
	for (auto& v : puncte) {
		if (v[2] == 0) {
			pair<int,int>a = get_max(v[1],NMAX - 1,1,NMAX,1);
			ans[v[3]] = a.first + 1;
			if (a.first == 0)
				dp[v[3]] = 1;
			else
				dp[v[3]] = a.second;
			}
		else {
			set_max(v[1],ans[v[3]],dp[v[3]],1,NMAX,1);
			}
		}
	int maxim = 0;
	int n = 0;
	for (int i = 1; i <= N;++i)
		maxim = max(maxim,ans[i]);
	for (int i = 1; i <= N;++i)
		if (maxim == ans[i])
			n = (n + dp[i]) % MOD;
	cout << maxim << ' ' << n << '\n';
	}

main() {
	solve();
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 100 / 100