Submission #91895

#TimeUsernameProblemLanguageResultExecution timeMemory
91895ngot23trapezoid (balkan11_trapezoid)C++11
45 / 100
1086 ms7380 KiB
#include <bits/stdc++.h> #define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i) #define mp make_pair #define PB push_back #define pii pair<int,int> #define F first #define S second #define Task "trapeze" using namespace std; const int N=100005; const int mod=30013; struct data { int rr, val, type, id; bool operator < (const data &X) const { return (rr<X.rr)||((rr==X.rr)&&(type>X.type)); } } b[N*2]; int n; pair <pii, pii > a[N]; vector <int > vt, vd; pii dp[N], ans; pii MAX(pii A, pii B) { if(A.F>B.F) return A; if(A.F<B.F) return B; A.S=(A.S+B.S)%mod; return A; } struct fenwicktree { pii t[N]; void update(int node, pii X) { while(node<=n*2) { t[node]=MAX(t[node], X); node+=node&(-node); } } pii get(int node) { pii ret=mp(0, 0); while(node>0) { ret=MAX(ret, t[node]); node-=node&(-node); } return ret; } } BIT; void setup() { cin >> n; rep(i, 1, n) { cin >> a[i].F.F >> a[i].F.S >> a[i].S.F >> a[i].S.S; vt.PB(a[i].F.F); vt.PB(a[i].F.S); vd.PB(a[i].S.F); vd.PB(a[i].S.S); } } int Find(vector <int > v, int val) { int id=lower_bound(v.begin(), v.end(), val)-v.begin()+1; return id; } void pre() { sort(vt.begin(), vt.end()); vt.resize(unique(vt.begin(), vt.end())-vt.begin()); sort(vd.begin(), vd.end()); vd.resize(unique(vd.begin(), vd.end())-vd.begin()); rep(i, 1, n) { a[i].F.F=Find(vt, a[i].F.F); a[i].S.F=Find(vd, a[i].S.F); b[i*2-1]={a[i].F.F, a[i].S.F, 1, i}; a[i].F.S=Find(vt, a[i].F.S); a[i].S.S=Find(vd, a[i].S.S); b[i*2]={a[i].F.S, a[i].S.S, -1, i}; } sort(b+1, b+n*2+1); } void calc() { rep(i, 1, n*2) { if(b[i].type==1) { int id=b[i].id; pii prv=BIT.get(b[i].val-1); dp[id]=mp(prv.F+1, prv.S); if(dp[id].F==1) dp[id].S=1; ans=MAX(ans, dp[id]); } else { int id=b[i].id; BIT.update(b[i].val, dp[id]); } } cout << ans.F << ' ' << ans.S; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen(Task".inp", "r", stdin); // freopen(Task".out", "w", stdout); setup(); pre(); calc(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...