Submission #308814

#	Time	Username	Problem	Language	Result	Execution time	Memory
308814		czhang2718	trapezoid (balkan11_trapezoid)	C++14	10 / 100	1094 ms	65544 KiB

trapezoid

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
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 tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> set_t;
typedef vector<int> vi;
const int MOD = 1e9+7;

int n, a, b, c, d;
map<int, int> endy;
map<int, int> x;
map<int, pii> 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);

  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;
  vi num(n+1);
  vector<set_t> vals(n+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, k};
    }
    else{
      int len=ans[y].first;
      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(num[i]){
      cout << i << " " << num[i];
      return 0;
    }
  }
}

• Subtask 1: 10 / 100