제출 #1265993

#제출 시각아이디문제언어결과실행 시간메모리
1265993dhuyyyytrapezoid (balkan11_trapezoid)C++20
4 / 100
1096 ms7136 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; using ll = long long; using ii = pair<int,int>; using pii = pair<int,ii>; using aa = array<int,4>; const int N = 1e5+5; const int INF = 1e9; const int MOD = 1e9+7; int n,ans,dp[N]; aa p[N]; vector <int> compress; struct SMT{ int n; vector<int> t; vector<int> lazy; SMT(int _n = 0) : n(_n){ t.assign((n << 2),0); lazy.assign((n << 2),0); } void push(int id,int l,int r){ if (l == r || !lazy[id]) return; for (int i = 0; i <= 1; i++){ t[id*2+i] += lazy[id]; lazy[id*2+i] += lazy[id]; } lazy[id] = 0; } void update(int id,int l,int r,int u,int v){ } }; int calc(int val){ return lower_bound(compress.begin(),compress.end(),val) - compress.begin(); } /* p[i][0]: l p[i][1]: r p[i][2]: l1 p[i][3]: r1 */ signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; i++){ for (int j = 0; j <= 3; j++){ cin >> p[i][j]; compress.push_back(p[i][j]); } } sort(p+1,p+1+n); sort(compress.begin(),compress.end()); compress.erase(unique(compress.begin(),compress.end()),compress.end()); dp[1] = 1; for (int i = 2; i <= n; i++){ for (int j = i - 1; j >= 1; j--){ if (p[j][1] < p[i][0] && p[j][3] < p[i][2]){ dp[i] = max(dp[i],dp[j] + 1); } } ans = max(ans,dp[i]); } cout << ans << ' ' << 0; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...