Submission #885567

#TimeUsernameProblemLanguageResultExecution timeMemory
885567serifefedartartrapezoid (balkan11_trapezoid)C++17
24 / 100
112 ms55312 KiB
#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 = 1e9 + 7; 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]; int fen[MAXN], dp[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; } 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]); } } cout << mx << " 0" << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...