oj.uz

Submission #1030213

# Submission time Handle Problem Language Result Execution time Memory
1030213 2024-07-21T23:27:49 Z ArshiaDadras trapezoid (balkan11_trapezoid) C++14
46 / 100
 119 ms 35772 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 = 1e9 + 7;
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
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Partially correct 10 ms 24132 KB Partially correct
4 Partially correct 11 ms 24152 KB Partially correct
5 Partially correct 11 ms 24156 KB Partially correct
6 Partially correct 12 ms 24156 KB Partially correct
7 Partially correct 15 ms 24440 KB Partially correct
8 Partially correct 17 ms 24640 KB Partially correct
9 Partially correct 20 ms 25276 KB Partially correct
10 Partially correct 31 ms 26652 KB Partially correct
11 Partially correct 35 ms 27336 KB Partially correct
12 Partially correct 61 ms 30660 KB Partially correct
13 Partially correct 74 ms 30868 KB Partially correct
14 Partially correct 86 ms 33012 KB Partially correct
15 Partially correct 88 ms 33048 KB Partially correct
16 Partially correct 106 ms 32860 KB Partially correct
17 Partially correct 104 ms 34588 KB Partially correct
18 Partially correct 97 ms 33728 KB Partially correct
19 Partially correct 105 ms 34160 KB Partially correct
20 Partially correct 119 ms 35772 KB Partially correct