Submission #417711

#TimeUsernameProblemLanguageResultExecution timeMemory
417711MarcoMeijertrapezoid (balkan11_trapezoid)C++14
100 / 100
229 ms49468 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e18 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // input template<class T> void IN(T& x) {cin >> x;} template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); } // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const vector<T>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);} template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } template<class H> void OUTLS(const H& h) {OUTL(h); } template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); } // dp template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;} template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;} void program(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); program(); } //===================// // begin program // //===================// const int MX = 5e5; const int N = (1<<20); const int MOD = 30013; int n; int a[MX], b[MX], c[MX], d[MX]; // fenwick tree int FT[MX]; void addFT(int i, int value) { for(i++; i<MX; i+=i&-i) FT[i] = max(FT[i],value); } int getFT(int i) { int ans = 0; for(i++; i; i-=i&-i) ans = max(ans, FT[i]); return ans; } int SM[MX]; void addSM(int i, int value) { for(i++; i<MX; i+=i&-i) SM[i] = (SM[i]+value)%MOD; } int getSM(int i) { int ans = 0; for(i++; i; i-=i&-i) ans = (ans+SM[i])%MOD; return ans; } // lis int lis[MX]; vi atA[MX], atB[MX]; vi layer[MX]; int dp[MX]; void program() { IN(n); RE(i,n) IN(a[i],b[i],c[i],d[i]); // coordinate compression vi difx; RE(i,n) difx.pb(a[i]), difx.pb(b[i]), difx.pb(c[i]), difx.pb(d[i]); sort(all(difx)); RE(i,n) { a[i] = lower_bound(all(difx),a[i]) - difx.begin(); b[i] = lower_bound(all(difx),b[i]) - difx.begin(); c[i] = lower_bound(all(difx),c[i]) - difx.begin(); d[i] = lower_bound(all(difx),d[i]) - difx.begin(); } // getting lis RE(i,n) atA[a[i]].pb(i); RE(i,n) atB[b[i]].pb(i); RE(i,n*4) { FOR(j,atA[i]) lis[j] = getFT(c[j]-1) + 1; FOR(j,atB[i]) addFT(d[j], lis[j]); } // getting dp RE(i,n) layer[lis[i]].pb(i); RE1(i,n) { priority_queue<iii,viii,greater<iii>> pq; FOR(j,layer[i-1]) pq.push({b[j],2,j}); FOR(j,layer[i]) pq.push({a[j],1,j}); while(!pq.empty()) { iii p = pq.top(); pq.pop(); int x, t, j; tie(x,t,j) = p; if(t == 1) { dp[j] = getSM(c[j]-1); if(i == 1) dp[j] = 1; } if(t == 2) addSM(d[j], dp[j]); } FOR(j,layer[i-1]) addSM(d[j],-dp[j]); } int ans=0, ans2=0; RE(i,n) ans = max(ans,lis[i]); RE(i,n) if(lis[i] == ans) ans2=(ans2+dp[i])%MOD; OUTLS(ans,ans2); }
#Verdict Execution timeMemoryGrader output
Fetching results...