Submission #309010

#	Time	Username	Problem	Language	Result	Execution time	Memory
309010		czhang2718	trapezoid (balkan11_trapezoid)	C++14	40 / 100	450 ms	18332 KiB

trapezoid

#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MOD = 1e9+7;

int n, a, b, c, d;
unordered_map<int, int> endy;
unordered_map<int, int> x;
unordered_map<int, int> ans;
vector<pii> pnts;

bool comp(pii a, pii b){
  return x[a.first]<x[b.first];
}

int main(){
  // freopen("input.txt", "r", stdin); 
  // freopen("output.txt", "w", stdout);
  cin.sync_with_stdio(0); cin.tie();
  cin.exceptions(cin.failbit);

  endy.reserve(100000);
  x.reserve(100000);
  ans.reserve(100000);
  cin >> n;
  rep(i, 1, n){
    cin >> a >> b >> c >> d;
    x[a]=c; x[b]=d;
    endy[a]=b;
    pnts.pb({a, 0});
    pnts.pb({b, 1});
  }
  sort(all(pnts), comp);

  vi lis(n+1);
  rep(i, 1, n) lis[i]=1e9+1;

  rep(i, 0, 2*n-1){
    int y=pnts[i].first;
    if(pnts[i].second==0){
      int len=upper_bound(all(lis), y)-lis.begin();
      // int k=(len==1?1:vals[len-1].order_of_key(y));
      ans[endy[y]]=len;
    }
    else{
      int len=ans[y];
      lis[len]=min(y, lis[len]);
      // num[len]+=ans[y].second;
      // rep(i, 1, ans[y].second) vals[len].insert(y);
    }
  }

  for(int i=n; i>0; i--){
    if(lis[i]<1e9+1){
      cout << i << " " << 5;
      return 0;
    }
  }
}

• Subtask 1: 40 / 100