제출 #1222748

#제출 시각아이디문제언어결과실행 시간메모리
1222748mariamtsagarelitrapezoid (balkan11_trapezoid)C++20
30 / 100
157 ms27248 KiB
#include <bits/stdc++.h> using namespace std; using i = int; const i MOD = 30013; struct Trap { i a, b, c, d; }; struct Seg { i mx, cnt; Seg(i m = 0, i c = 0): mx(m), cnt(c) {} }; Seg mergeSeg(const Seg &x, const Seg &y) { if (x.mx > y.mx) return x; if (y.mx > x.mx) return y; if (x.mx == 0) return Seg(0, 1); return Seg(x.mx, (x.cnt + y.cnt) % MOD); } struct ST { i n; vector<Seg> t; ST(i m): n(m), t(4*m+4, Seg(0,1)) {} Seg queryRec(i p, i l, i r, i ql, i qr) { if (r < ql || l > qr) return Seg(0,1); if (ql <= l && r <= qr) return t[p]; i m = (l + r) >> 1; return mergeSeg( queryRec(p<<1, l, m, ql, qr), queryRec(p<<1|1, m+1, r, ql, qr) ); } Seg query(i l, i r) { return l > r ? Seg(0,1) : queryRec(1,1,n,l,r); } void updateRec(i p, i l, i r, i pos, const Seg &v) { if (l == r) { t[p] = mergeSeg(t[p], v); return; } i m = (l + r) >> 1; if (pos <= m) updateRec(p<<1, l, m, pos, v); else updateRec(p<<1|1, m+1, r, pos, v); t[p] = mergeSeg(t[p<<1], t[p<<1|1]); } void update(i pos, const Seg &v) { updateRec(1,1,n,pos,v); } }; struct BIT { i n; vector<i> f; BIT(i m): n(m), f(m+1,0) {} void add(i pos, i v) { for (; pos <= n; pos += pos & -pos) f[pos] = (f[pos] + v) % MOD; } i sum(i pos) { i s = 0; for (; pos > 0; pos -= pos & -pos) s = (s + f[pos]) % MOD; return s; } }; int main() { ios::sync_with_stdio(false); cin.tie(NULL); i N; cin >> N; vector<Trap> A(N); vector<i> C; C.reserve(4*N); for (i idx = 0; idx < N; idx++) { cin >> A[idx].a >> A[idx].b >> A[idx].c >> A[idx].d; C.push_back(A[idx].a); C.push_back(A[idx].b); C.push_back(A[idx].c); C.push_back(A[idx].d); } sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end()); auto id = [&](i v){ return (i)(lower_bound(C.begin(), C.end(), v) - C.begin() + 1); }; i M = C.size(); for (auto &t : A) { t.a = id(t.a); t.b = id(t.b); t.c = id(t.c); t.d = id(t.d); } sort(A.begin(), A.end(), [](const Trap &x, const Trap &y){ return x.a != y.a ? x.a < y.a : x.b < y.b; }); ST stTop(M), stBot(M); vector<Seg> dp(N); for (i idx = 0; idx < N; idx++) { Seg leftBest = stTop.query(1, A[idx].a - 1); Seg downBest = stBot.query(1, A[idx].c - 1); Seg cur = mergeSeg(leftBest, downBest); dp[idx] = Seg(cur.mx + 1, cur.cnt); stTop.update(A[idx].b, dp[idx]); stBot.update(A[idx].d, dp[idx]); } i K = 0; for (auto &s : dp) K = max(K, s.mx); vector<vector<i>> by(K+1); for (i idx = 0; idx < N; idx++) by[dp[idx].mx].push_back(idx); vector<i> cnt2(N); for (i k = 1; k < K; k++) { BIT bit(M); for (i idx : by[k]) bit.add(A[idx].d, dp[idx].cnt); for (i idx : by[k+1]) cnt2[idx] = bit.sum(A[idx].c - 1); for (i idx : by[k+1]) dp[idx].cnt = cnt2[idx]; } i total = 0; for (i idx : by[K]) total = (total + dp[idx].cnt) % MOD; cout << K << " " << total; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...