Submission #1030213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030213		ArshiaDadras	trapezoid (balkan11_trapezoid)	C++14	46 / 100	119 ms	35772 KiB

trapezoid

/* 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 (stderr)

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 / 100