Submission #1079587

#TimeUsernameProblemLanguageResultExecution timeMemory
1079587codexistenttrapezoid (balkan11_trapezoid)C++14
0 / 100
40 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define MOD 30013 #define FOR(i, a, b) for(int i = a; i <= b; i++) #define f first #define s second int n, stc[MAXN * 2 * 4], stn[MAXN * 2 * 4]; pair<int, int> sp[MAXN], ep[MAXN], dp[MAXN]; queue<pair<int, int>> lz[MAXN * 2 * 4]; void push_n(int i, int l, int r){ while(!lz[i].empty()){ auto lzi = lz[i].front(); lz[i].pop(); // if(lzi.f != 0) cout << " MGMGMG " << i << " => " << (stn[i] * (lzi.f != 0) + lzi.s) << endl; stn[i] = (stn[i] * (lzi.f != 0) + lzi.s) % MOD; if(l != r) lz[i * 2].push(lzi), lz[i * 2 + 1].push(lzi); } } int query_n(int i, int l, int r, int qry){ push_n(i, l, r); if(qry < l || r < qry) return 0; if(l == r) return stn[i]; return (query_n(i * 2, l, (l + r) / 2, qry) + query_n(i * 2 + 1, (l + r) / 2 + 1, r, qry)) % MOD; } void update_n(int i, int l, int r, pair<int, int> rng, pair<int, int> upd){ // if(rng.f == 5 && rng.s == 14) cout << "HERE -> " << i << " of rng " << l << " " << r << endl; push_n(i, l, r); if(rng.s < l || r < rng.f) return; if(rng.f <= l && r <= rng.s) { // cout << " \--> HERERO " << endl; lz[i].push(upd); push_n(i, l, r); return; } update_n(i * 2, l, (l + r) / 2, rng, upd); update_n(i * 2 + 1, (l + r) / 2 + 1, r, rng, upd); } int query_c(int i, int l, int r, pair<int, int> rng){ if(rng.second < l || r < rng.first) return 0; if(rng.first <= l && r <= rng.second) return stc[i]; return max(query_c(i * 2, l, (l + r) / 2, rng), query_c(i * 2 + 1, (l + r) / 2 + 1, r, rng)); } void update_c(int i, int l, int r, pair<int, int> upd){ if(upd.f < l || r < upd.f) return; if(l == r) { stc[i] = upd.s; return; } update_c(i * 2, l, (l + r) / 2, upd); update_c(i * 2 + 1, (l + r) / 2 + 1, r, upd); stc[i] = max(stc[i * 2], stc[i * 2 + 1]); } int main(){ cin >> n; vector<pair<int, pair<int, int>>> ple; FOR(i, 1, n){ cin >> sp[i].f >> ep[i].f; cin >> sp[i].s >> ep[i].s; ple.push_back({sp[i].s, {0, i}}); ple.push_back({ep[i].s, {1, i}}); } // coordinate compression vector<pair<int, pair<int, int>>> pls; sort(begin(ple), end(ple)); FOR(i, 1, 2 * n){ if(ple[i - 1].s.f == 0){ sp[ple[i - 1].s.s].s = i; pls.push_back({sp[ple[i - 1].s.s].f, {0, ple[i - 1].s.s}}); }else{ ep[ple[i - 1].s.s].s = i; pls.push_back({ep[ple[i - 1].s.s].f, {1, ple[i - 1].s.s}}); } } sort(begin(pls), end(pls)); FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0; update_n(1, 0, 2 * n, {0, 2 * n}, {0, 1}); /* FOR(i, 0, 2*n){ cout << " " << query_n(1, 0, 2*n, i); } cout << endl; FOR(i, 0, 2*n){ cout << " " << query_c(1, 0, 2*n, {i, i}); } cout << endl; */ for(auto pi : pls){ int i = pi.s.s; if(pi.s.f == 0){ // start point dp[i].f = query_c(1, 0, 2 * n, {0, sp[i].s - 1}) + 1; dp[i].s = query_n(1, 0, 2 * n, sp[i].s - 1) % MOD; // cout << "DP " << i << " EQUALS " << dp[i].f << " of ct " << dp[i].s << endl; }else{ int qi = query_c(1, 0, 2 * n, {0, ep[i].s - 1}); if(qi > dp[i].f) goto update; int lo = ep[i].s, hi = 2 * n; if(qi < dp[i].f){ while(lo < hi){ int mid = (lo + hi + 1) / 2; // cout << " FINDING NEMOi FOR THE BELOW " << 0 << " to " << mid << " GIVES " << query_c(1, 0, 2 * n, {0, mid}) << endl; if(query_c(1, 0, 2 * n, {0, mid}) < dp[i].f){ lo = mid; }else{ hi = mid - 1; } } // replace num valid ways with dp[i].s for range (ep[i].s)...lo update_n(1, 0, 2 * n, {ep[i].s, lo}, {0, dp[i].s}); // cout << " ALERT 1: we update " << ep[i].s << " TO " << lo << " with complete refurbish to " << dp[i].s << endl; /* FOR(i, 0, 2*n){ cout << " " << query_n(1, 0, 2*n, i); } cout << endl; FOR(i, 0, 2*n){ cout << " " << query_c(1, 0, 2*n, {i, i}); } cout << endl; */ if(lo == 2 * n) goto update; lo ++; } int si = lo; if(query_c(1, 0, 2 * n, {0, lo}) != dp[i].f) goto update; hi = 2 * n; while(lo < hi){ // cout << ((lo + hi) / 2) << " => " << query_c(i, 0, 2 * n, {0, (lo + hi) / 2}) << endl; int mid = (lo + hi + 1) / 2; if(query_c(1, 0, 2 * n, {0, mid}) == dp[i].f){ lo = mid; }else{ hi = mid - 1; } } // add num valid ways with dp[i].s for range si...lo update_n(1, 0, 2 * n, {si, lo}, {1, dp[i].s}); /*cout << " ALERT 2: we update " << si << " TO " << lo << " with add to " << dp[i].s << endl; FOR(j, 0, 2*n){ cout << " " << query_n(1, 0, 2*n, j); } cout << endl; FOR(j, 0, 2*n){ cout << " " << query_c(1, 0, 2*n, {j, j}); } cout << endl;*/ } update:; if(pi.s.f == 1) { // cout << " => " << dp[i].f << endl; update_c(1, 0, 2 * n, {ep[i].s, dp[i].f}); /* cout << " ALERT 3" << endl; FOR(i, 0, 2*n){ cout << " " << query_c(1, 0, 2*n, {i, i}); } cout << endl; */ } } int cr = query_c(1, 0, 2 * n, {0, 2 * n}); cout << cr; int nr = 0; FOR(i, 1, n) if(dp[i].f == cr) nr = (nr + dp[i].s) % MOD; cout << " " << nr << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...