oj.uz

답안 #1030214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030214 2024-07-21T23:28:47 Z ArshiaDadras 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 113 ms 35744 KB 
/* In the name of Allah */
// Welcome to the Soldier Side!
// Where there's no one here, but me...
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, P = 30013;
vector<int> L[2 * N], R[2 * N], vec[N];
int n, a[N], b[N], c[N], d[N], dp[N], cnt[N];
struct MaxFenwickTree {
	int fen[2 * N];

	void add(int p, int k) {
		for (; p < 2 * N; p += p & -p)
			fen[p] = max(fen[p], k);
	}
	int get(int p) {
		int res = 0;
		for (; p; p -= p & -p)
			res = max(res, fen[p]);
		return res;
	}
} T1;
struct SumFenwickTree {
	int fen[2 * N];
	vector<int> history;

	void add(int p, int k) {
		history.push_back(p);
		for (p++; p < 2 * N; p += p & -p)
			(fen[p] += k) %= P;
	}
	int get(int p) {
		int res = 0;
		for (p++; p; p -= p & -p)
			(res += fen[p]) %= P;
		return res;
	}
	void rollback() {
		for (int p: history)
			for (p++; p < 2 * N; p += p & -p)
				fen[p] = 0;
		history.clear();
	}
} T2;

void compress(int x[], int y[]) {
	vector<int> help;
	for (int i = 0; i < n; i++) {
		help.push_back(x[i]);
		help.push_back(y[i]);
	}

	sort(help.begin(), help.end());
	help.resize(unique(help.begin(), help.end()) - help.begin());
	for (int i = 0; i < n; i++) {
		x[i] = lower_bound(help.begin(), help.end(), x[i]) - help.begin();
		y[i] = lower_bound(help.begin(), help.end(), y[i]) - help.begin();
	}
}

void read_input() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
}

void solve() {
	compress(a, b), compress(c, d);
	for (int i = 0; i < n; i++) {
		L[a[i]].push_back(i);
		R[b[i]].push_back(i);
	}

	for (int i = 0; i < 2 * n; i++) {
		for (int p: R[i])
			T1.add(d[p], dp[p]);
		for (int p: L[i])
			dp[p] = T1.get(c[p]) + 1;
	}

	fill(cnt, cnt + n, 1);
	for (int i = 0; i < n; i++)
		vec[dp[i]].push_back(i);
	for (int i = 2; i <= n; i++) {
		vector<pair<int, int>> help;
		for (int p: vec[i - 1])
			help.push_back({b[p], p});
		for (int p: vec[i])
			help.push_back({a[p], p});

		T2.rollback();
		sort(help.begin(), help.end());
		for (auto [_, p]: help)
			if (dp[p] < i)
				T2.add(d[p], cnt[p]);
			else
				cnt[p] = T2.get(c[p]);
	}
}

void write_output() {
	int ted = 0;
	int k = *max_element(dp, dp + n);
	for (int p: vec[k])
		(ted += cnt[p]) %= P;
	cout << k << " " << ted << endl;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}

Compilation message

trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:94:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |   for (auto [_, p]: help)
      |             ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 24068 KB Output is correct
3 Correct 12 ms 23896 KB Output is correct
4 Correct 11 ms 24012 KB Output is correct
5 Correct 11 ms 24156 KB Output is correct
6 Correct 11 ms 24156 KB Output is correct
7 Correct 13 ms 24412 KB Output is correct
8 Correct 15 ms 24572 KB Output is correct
9 Correct 21 ms 25156 KB Output is correct
10 Correct 29 ms 26660 KB Output is correct
11 Correct 34 ms 27256 KB Output is correct
12 Correct 62 ms 30276 KB Output is correct
13 Correct 70 ms 30900 KB Output is correct
14 Correct 91 ms 32944 KB Output is correct
15 Correct 91 ms 32816 KB Output is correct
16 Correct 92 ms 32864 KB Output is correct
17 Correct 100 ms 33876 KB Output is correct
18 Correct 103 ms 33644 KB Output is correct
19 Correct 103 ms 34188 KB Output is correct
20 Correct 113 ms 35744 KB Output is correct