Submission #1264504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264504		zNatsumi	trapezoid (balkan11_trapezoid)	C++17	43 / 100	179 ms	47268 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;

const int N = 1e5 + 5;

int n, m;
ii dp[N];
vector<int> rrh;
vector<int> Lbound[N*4], Rbound[N*4];

struct info{
  int a, b, c, d;
  info(){}
  info(int a, int b, int c, int d): a(a), b(b), c(c), d(d) {}
} x[N];

void init(){
  for(int i = 1; i <= n; i++)
    for(auto y : {x[i].a, x[i].b, x[i].c, x[i].d}) rrh.push_back(y);
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());

  for(int i = 1; i <= n; i++){
    x[i].a = lower_bound(rrh.begin(), rrh.end(), x[i].a) - rrh.begin() + 1;
    x[i].b = lower_bound(rrh.begin(), rrh.end(), x[i].b) - rrh.begin() + 1;
    x[i].c = lower_bound(rrh.begin(), rrh.end(), x[i].c) - rrh.begin() + 1;
    x[i].d = lower_bound(rrh.begin(), rrh.end(), x[i].d) - rrh.begin() + 1;

    Lbound[x[i].a].push_back(i);
    Rbound[x[i].b].push_back(i);
  }
  m = rrh.size();
}

void add(int &x, int y){
  x = (x + y) % 2023;
}

namespace it{
  ii st[N<<4];

  ii _merge(ii x, ii y){
    ii res = {0, 0};
    res.first = max(x.first, y.first);
    if(res.first == x.first) add(res.second, x.second);
    if(res.first == y.first) add(res.second, y.second);
    return res;
  }

  void update(int pos, ii val, int tl = 0, int tr = m, int i = 1){
    if(tl == tr){
      if(val.first > st[i].first) st[i] = {val.first, 0};
      if(st[i].first == val.first) add(st[i].second, val.second);
      return;
    }
    int tm = tl + tr >> 1;
    if(pos <= tm) update(pos, val, tl, tm, i<<1);
    else update(pos, val, tm + 1, tr, i<<1|1);
    st[i] = _merge(st[i<<1], st[i<<1|1]);
  }
  ii get(int l, int r, int tl = 0, int tr = m, int i = 1){
    if(r < tl || tr < l || l > r) return {0, 0};
    if(l <= tl && tr <= r) return st[i];
    int tm = tl + tr >> 1;
    return _merge(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++){
    int a, b, c, d; cin >> a >> b >> c >> d;
    x[i] = info(a, b, c, d);
  }
  init();
  it::update(0, {0, 1});

  int res = 0, cnt = 0;
  for(int t = 1; t <= m; t++){
    for(auto idx : Rbound[t]){
      auto [a, b, c, d] = x[idx];
      it::update(d, dp[idx]);
    }
    for(auto idx : Lbound[t]){
      auto [a, b, c, d] = x[idx];
      dp[idx] = it::get(0, c);
      dp[idx].first += 1;

      if(dp[idx].first > res) res = dp[idx].first, cnt = 0;
      if(dp[idx].first == res) add(cnt, dp[idx].second);
    }
  }

  cout << res << " " << cnt << "\n";
}

• Subtask 1: 43 / 100