Submission #1079638

#TimeUsernameProblemLanguageResultExecution timeMemory
1079638codexistenttrapezoid (balkan11_trapezoid)C++14
58 / 100
204 ms13628 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]; pair<int, int> sp[MAXN], ep[MAXN]; pair<int, short> dp[MAXN]; 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]); } void update_n(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_n(i * 2, l, (l + r) / 2, upd); update_n(i * 2 + 1, (l + r) / 2 + 1, r, upd); stc[i] = (stc[i * 2] + stc[i * 2 + 1]) % MOD; } int query_n(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 (query_n(i * 2, l, (l + r) / 2, rng) + query_n(i * 2 + 1, (l + r) / 2 + 1, r, rng)) % MOD; } 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] = 0; /* 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; // 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 // 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 /*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:; */else { // 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; */ } } // FOR(i, 1, n) cout << dp[i].f << endl; priority_queue<pair<int, pair<int, int>>> pq; FOR(i, 1, n) pq.push({-dp[i].f, {-sp[i].f, i}}); FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = 0; dp[0].s = 1, ep[0].s = 0; update_n(1, 0, 2*n, {0, 1}); /*FOR(i, 0, 2*n){ cout << " " << query_n(1, 0, 2*n, {i, i}); } cout << endl;*/ int prv = pq.top().f, ptr = 1; vector<pair<int, int>> v2p, vp; v2p.push_back({0, 0}); while(pq.size()){ // cout << "QUERY " << -pq.top().f << " ~ " << -pq.top().s.f << " => " << pq.top().s.s << endl; if(pq.top().f != prv){ // cout << -pq.top().f << " " << endl; for(auto i : v2p) { update_n(1, 0, 2 * n, {ep[i.s].s, 0}); // cout << " " << i.s << " "; } ptr = 0; // cout << endl; v2p.clear(); swap(v2p, vp); sort(begin(v2p), end(v2p)); } prv = pq.top().f; int i = pq.top().s.s; pq.pop(); while(ptr != v2p.size() && v2p[ptr].f < sp[i].f){ update_n(1, 0, 2 * n, {ep[v2p[ptr].s].s, dp[v2p[ptr].s].s}); ptr++; } dp[i].s = query_n(1, 0, 2 * n, {0, sp[i].f - 1}); vp.push_back({ep[i].f, i}); /*FOR(i, 0, 2*n){ cout << " " << query_n(1, 0, 2*n, {i, i}); } cout << endl;*/ } int cr = 0; FOR(i, 1, n) cr = max(cr, dp[i].f); cout << cr; int nr = 0; FOR(i, 1, n) if(dp[i].f == cr) nr = (nr + dp[i].s) % MOD; cout << " " << nr << endl; }

Compilation message (stderr)

trapezoid.cpp:107:17: warning: "/*" within comment [-Wcomment]
  107 |                 /* FOR(i, 0, 2*n){
      |                  
trapezoid.cpp:136:13: warning: "/*" within comment [-Wcomment]
  136 |             /*cout << " ALERT 2: we update " << si << " TO " << lo << " with add to " << dp[i].s << endl;
      |              
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:196:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         while(ptr != v2p.size() && v2p[ptr].f < sp[i].f){
      |               ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...