Submission #1230463

#TimeUsernameProblemLanguageResultExecution timeMemory
1230463pannenkoek사다리꼴 (balkan11_trapezoid)C++20
14 / 100
509 ms62544 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = (a); i < (b); i++) #define pb push_back #define fi first #define se second using ll = long long; using ld = long double; using pii = pair<ll, ll>; const int MAXN = 1e5 + 5; int n, N; array<int, 4> points[MAXN]; set<vector<int>> events; set<int> num; map<int, int> compress; pii seg[MAXN * 16]; pii smaller[MAXN]; pii comp(pii a, pii b){ if(a.fi == b.fi) return {a.fi, a.se + b.se}; if(a.fi > b.fi) return a; return b; } void insert(int i, int l, int r, int pos, pii val){ if(l == r){ seg[i] = comp(seg[i], val); return; } int mid = (l + r) / 2; if(pos <= mid) insert(i * 2, l, mid, pos, val); else insert(i * 2 + 1, mid + 1, r, pos, val); seg[i] = comp(seg[i * 2], seg[i * 2 + 1]); } pii query(int i, int l, int r, int ql, int qr){ if(qr < l || ql > r) return {0, 0}; if(ql <= l && r <= qr) return seg[i]; int mid = (l + r) / 2; if(qr <= mid) return query(i * 2, l, mid, ql, qr); if(ql > mid) return query(i * 2 + 1, mid + 1, r, ql, qr); return comp(query(i * 2, l, mid, ql, qr), query(i * 2 + 1, mid + 1, r, ql, qr)); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; rep(i, 0, n){ int a, b, c, d; cin >> a >> b >> c >> d; points[i] = {a, b, c, d}; events.insert({a, 1, i}); events.insert({b, 2, i}); num.insert(a); num.insert(b); num.insert(c); num.insert(d); } int cnt = 1; for(auto x : num) compress[x] = cnt++; N = 1; while(N < cnt) N *= 2; insert(1, 0, N - 1, 0, {0, 1}); for(auto event : events){ int type = event[1]; int i = event[2]; auto [a, b, c, d] = points[i]; a = compress[a]; b = compress[b]; c = compress[c]; d = compress[d]; if(type == 1){ smaller[i] = query(1, 0, N - 1, 0, c - 1); smaller[i].fi += 1; } else { insert(1, 0, N - 1, d, smaller[i]); } } pii res = query(1, 0, N - 1, 0, N - 1); cout << res.fi << " " << res.se << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...