제출 #1016995

#제출 시각아이디문제언어결과실행 시간메모리
1016995dosts사다리꼴 (balkan11_trapezoid)C++17
12 / 100
130 ms30404 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define vi vector<int> #define all(xx) xx.begin(),xx.end() const int N = 1e6+1,inf = 2e9,B = 23,MOD = 30013,LIM = 1e9; struct T { int a,b,c,d; }; int add(int x,int y){ return ((x+y) >= MOD ? x+y-MOD : x+y); } struct ST { vi t; ST(int nn) { t.assign(4*nn+1,0); } int query(int node,int l,int r,int L,int R) { if (l > R || r < L) return 0; if (l >= L && r <= R) return t[node]; int m = (l+r) >> 1; return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R)); } void update(int node,int l,int r,int p,int v) { if (l == r) { t[node] = max(t[node],v); return; } int m = (l+r) >> 1; if (p<=m) update(2*node,l,m,p,v); else update(2*node+1,m+1,r,p,v); t[node] = max(t[2*node],t[2*node+1]); } }; void solve() { int n; cin >> n; T traps[n+1]; for (int i=1;i<=n;i++) cin >> traps[i].a >> traps[i].b >> traps[i].c >> traps[i].d; vi v; for (int i=1;i<=n;i++) { v.push_back(traps[i].a); v.push_back(traps[i].b); v.push_back(traps[i].c); v.push_back(traps[i].d); } sort(v.begin(),v.end()); v.erase(unique(all(v)),v.end()); for (int i=1;i<=n;i++) { traps[i].a = upper_bound(all(v),traps[i].a)-v.begin(); traps[i].b = upper_bound(all(v),traps[i].b)-v.begin(); traps[i].c = upper_bound(all(v),traps[i].c)-v.begin(); traps[i].d = upper_bound(all(v),traps[i].d)-v.begin(); } sort(traps+1,traps+n+1,[&](const T& t1,const T& t2) { return t1.a < t2.a; });; int sz = v.size(); vector<pii> dp(n+1); ST st(sz); set<pii> fat_arrays[n+1]; for (int i=n;i>=1;i--) { //cout << "TRAP" sp traps[i].a sp traps[i].b sp traps[i].c sp traps[i].d << endl; int mn = max(traps[i].b,traps[i].d)+1; //mn..lim de en iyi dp valuesu dp[i].first = st.query(1,1,sz,mn,sz)+1; int cont = 0; auto it = fat_arrays[dp[i].ff-1].lower_bound({mn,-inf}); if (fat_arrays[dp[i].ff-1].empty() || it == fat_arrays[dp[i].ff-1].begin()) cont = 0; else { --it; cont = it->second; } dp[i].second = cont; if (dp[i].first == 1) dp[i].second = add(dp[i].second,1); fat_arrays[dp[i].first].insert({i,dp[i].second}); st.update(1,1,sz,traps[i].c,dp[i].first); //cout << dp[i].ff sp dp[i].ss << endl; }; int mx = 0; for (int i=1;i<=n;i++) mx = max(mx,dp[i].ff); int sm = 0; for (int i=1;i<=n;i++) if (dp[i].ff == mx) sm = add(sm,dp[i].ss); cout << mx sp sm << '\n'; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...