Submission #106146

#TimeUsernameProblemLanguageResultExecution timeMemory
106146Kewotrapezoid (balkan11_trapezoid)C++17
90 / 100
537 ms46328 KiB
#include <bits/stdc++.h> #define pb push_back #define ppb pop_back #define fi first #define se second #define mid ((x + y) / 2) #define left (ind * 2) #define right (ind * 2 + 1) #define timer ((double)clock() / CLOCKS_PER_SEC) #define endl "\n" #define spc " " #define d1(x) cerr<<#x<<":"<<x<<endl #define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl #define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl #define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long int lli; typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<double, double> dd; const int N = (int)(1e6 + 5); const int LOG = (int)(20); const int mod = (int)(30013); int n, ans, tot; ii tree[N << 2], dp[N]; set<int> s; unordered_map<int, int> mp; vector<ii> ev; struct trap { int a, b, c, d; void read() { cin >> a >> b >> c >> d; } void compress() { a = mp[a]; b = mp[b]; c = mp[c]; d = mp[d]; } }ar[N]; ii merge(ii x, ii y) { ii re; if(x.fi == y.fi) return {x.fi, (x.se + y.se) % mod}; else return max(x, y); } void upd(int ind, int x, int y, int a, ii val) { if(a < x || y < a) return; if(x == y) { tree[ind] = val; return; } upd(left, x, mid, a, val); upd(right, mid + 1, y, a, val); tree[ind] = merge(tree[left], tree[right]); } ii get(int ind, int x, int y, int a, int b) { if(y < a || b < x) return {-1, 0}; if(a <= x && y <= b) return tree[ind]; return merge(get(left, x, mid, a, b), get(right, mid + 1, y, a, b)); } int main() { fast_io(); //freopen("inp.in", "r", stdin); cin >> n; for(int i = 1; i <= n; i++) { ar[i].read(); s.insert(ar[i].a); s.insert(ar[i].b); s.insert(ar[i].c); s.insert(ar[i].d); } int t = 0; for(auto i : s) mp[i] = ++t; for(int i = 1; i <= n; i++) ar[i].compress(); for(int i = 1; i <= n; i++) { ev.pb({i, 0}); ev.pb({i, 1}); } sort(ev.begin(), ev.end(), [&] (ii x, ii y) { int cmpx, cmpy; if(x.se == 0) cmpx = ar[x.fi].c; else cmpx = ar[x.fi].d; if(y.se == 0) cmpy = ar[y.fi].c; else cmpy = ar[y.fi].d; return cmpx < cmpy; }); upd(1, 0, t, 0, {0, 1}); for(auto i : ev) { int ind = i.fi; if(i.se == 0) { ii g = get(1, 0, t, 0, ar[ind].a - 1); dp[ind] = {g.fi + 1, g.se}; } else upd(1, 0, t, ar[ind].b, dp[ind]); ans = max(ans, dp[ind].fi); } for(int i = 1; i <= n; i++) if(dp[i].fi == ans) { tot += dp[i].se; tot %= mod; } cout << ans << spc << tot; }
#Verdict Execution timeMemoryGrader output
Fetching results...