제출 #309501

#제출 시각아이디문제언어결과실행 시간메모리
309501caoash사다리꼴 (balkan11_trapezoid)C++14
26 / 100
249 ms64264 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; #define pb push_back #define rsz resize #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() using pi = pair<int,int>; #define f first #define s second #define mp make_pair const int MX = 100005; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(long double x) { cout << x; } void pr(char x) { cout << x; } void pr(const char * x) { cout << x; } void pr(const string & x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x); template < class T > void pr(const T & x); template < class T, class...Ts > void pr(const T & t, const Ts & ...ts) { pr(t); pr(ts...); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x) { pr("{", x.f, ", ", x.s, "}"); } template < class T > void pr(const T & x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template < class T, class...Ts > void ps(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { cout << "]" << endl; } // debug w/ commas template < class T, class...Ts > void pc(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[", #x, "] = ["), pc(x); } #ifdef LOCAL using namespace output; #endif #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; struct chash{ template <class T1, class T2> size_t operator()(const pair<T1, T2>& p) const { auto hash1 = hash<T1>{}(p.first); auto hash2 = hash<T2>{}(p.second); return hash1 ^ hash2; } }; unordered_map<int, int> cx, cy; map<pi, pi> st; map<pi, int> dp; template<int SZ> struct Seg { int tree[4*SZ]; int merge(int a, int b){ return max(a, b); } void update(int v, int l, int r, int i, int x) { if (i > r || i < l) { return; } else if (l == r) { tree[v] = x; return; } else { int m = (l + r) / 2; update(2 * v + 1, l, m, i, x); update(2 * v + 2, m + 1, r, i, x); tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]); } } int query(int v, int l, int r, int ql, int qr) { if (l > qr || r < ql) { return 0; } else if (l >= ql && r <= qr) { return tree[v]; } else { int m = (l + r) / 2; int a = query(2 * v + 1, l, m, ql, qr); int b = query(2 * v + 2, m + 1, r, ql, qr); return merge(a, b); } } }; Seg<MX> orz; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vi xs, ys; vector<pair<pi, int>> evts; for (int i = 0; i < n; i++) { int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2; pi lf = mp(x1, y1); pi sf = mp(x2, y2); st[sf] = lf; xs.pb(x1), ys.pb(y1); xs.pb(x2), ys.pb(y2); evts.pb(mp(lf, 0)); evts.pb(mp(sf, 1)); } sort(all(xs)); sort(all(ys)); int pt = 0; for (auto v : xs) cx[v] = pt++; pt = 0; for (auto v : ys) cy[v] = pt++; sort(all(evts)); for (auto curr : evts) { pi rd = mp(cx[curr.f.f], cy[curr.f.s]); if (curr.s) { pi prev = st[curr.f]; dp[rd] = dp[mp(cx[prev.f], cy[prev.s])]; orz.update(0, 0, sz(cy), rd.s, dp[rd]); } else { dp[rd] = orz.query(0, 0, sz(cy), 0, rd.s) + 1; } // dbg(curr.f, curr.s, st[curr.f], dp[curr.f]); } int ans = orz.query(0, 0, sz(cy), 0, sz(cy)); cout << ans << " " << 1 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...