oj.uz

답안 #885617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
885617 2023-12-10T10:19:26 Z serifefedartar 사다리꼴 (balkan11_trapezoid) C++17
46 / 100
 148 ms 44100 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 30013;
const ll LOGN = 21;
const ll MAXN = 4e5 + 100;

struct T {
	int a, b, c, d;
	void read() {
		cin >> a >> b >> c >> d;
	}
	T() { }
};
vector<T> trap;
vector<int> cc, in[MAXN], out[MAXN], x[MAXN];
int fen[MAXN], dp[MAXN], ways[MAXN];
void add(int k, int val) {
	while (k < MAXN) {
		fen[k] = max(fen[k], val);
		k += k & -k;
	}
}

int query(int k) {
	int mx = 0;
	while (k) {
		mx = max(mx, fen[k]);
		k -= k & -k;
	}
	return mx;
}

void addS(int k, int val) {
	while (k < MAXN) {
		fen[k] += val;
		k += k & -k;
	}
}

void setS(int k, int val) {
	while (k < MAXN) {
		fen[k] = val;
		k += k & -k;
	}
}

int queryS(int k) {
	int sum = 0;
	while (k) {
		sum += fen[k];
		k -= k & -k;
	}
	return sum;
}

int main() {
	fast
	int N;
	cin >> N;

	trap = vector<T>(N);
	for (int i = 0; i < N; i++) {
		trap[i].read();
		cc.push_back(trap[i].a);
		cc.push_back(trap[i].b);
		cc.push_back(trap[i].c);
		cc.push_back(trap[i].d);
	}
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	for (auto &u : trap) {
		u.a = upper_bound(cc.begin(), cc.end(), u.a) - cc.begin();
		u.b = upper_bound(cc.begin(), cc.end(), u.b) - cc.begin();
		u.c = upper_bound(cc.begin(), cc.end(), u.c) - cc.begin();
		u.d = upper_bound(cc.begin(), cc.end(), u.d) - cc.begin();
	}
	for (int i = 0; i < N; i++) {
		in[trap[i].a].push_back(i);
		out[trap[i].b].push_back(i);
	}

	int mx = 0;
	for (int i = 1; i < MAXN; i++) {
		for (auto u : out[i])
			add(trap[u].d, dp[u]);
		for (auto u : in[i]) {
			int Q = query(trap[u].c);
			dp[u] = Q + 1;
			mx = max(mx, dp[u]);
		}
	}

	for (int i = 0; i < N; i++) {
		x[dp[i]].push_back(i);
	}
	memset(fen, 0, sizeof(fen));
	for (int i = 0; i < MAXN; i++)
		in[i].clear(), out[i].clear();

	for (auto u : x[1])
		ways[u] = 1;

	int ans = x[1].size();
	for (int i = 2; i <= mx; i++) {
		int sum = 0;
		vector<pair<int,int>> v;
		for (auto u : x[i-1])
			v.push_back({trap[u].b, u});
		for (auto u : x[i])
			v.push_back({trap[u].a, u});
		sort(v.begin(), v.end());

		for (auto u : v) {
			if (dp[u.s] == i) {
				ways[u.s] = queryS(trap[u.s].c);
				sum += ways[u.s];
			} else
				addS(trap[u.s].d, ways[u.s]);
		}

		ans = max(ans, sum);
		for (auto u : v)
			setS(trap[u.s].d, 0);
	}
	cout << mx << " " << ans << "\n";
}

Subtask #1
46.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 32088 KB Output is correct
2 Correct 10 ms 32092 KB Output is correct
3 Partially correct 10 ms 32088 KB Partially correct
4 Partially correct 11 ms 32344 KB Partially correct
5 Partially correct 12 ms 32348 KB Partially correct
6 Partially correct 13 ms 32816 KB Partially correct
7 Partially correct 17 ms 32656 KB Partially correct
8 Partially correct 16 ms 32860 KB Partially correct
9 Partially correct 21 ms 33328 KB Partially correct
10 Partially correct 31 ms 34768 KB Partially correct
11 Partially correct 45 ms 35344 KB Partially correct
12 Partially correct 71 ms 38380 KB Partially correct
13 Partially correct 86 ms 39376 KB Partially correct
14 Partially correct 102 ms 40648 KB Partially correct
15 Partially correct 115 ms 41264 KB Partially correct
16 Partially correct 123 ms 41936 KB Partially correct
17 Partially correct 129 ms 42608 KB Partially correct
18 Partially correct 119 ms 42956 KB Partially correct
19 Partially correct 131 ms 43452 KB Partially correct
20 Partially correct 148 ms 44100 KB Partially correct