Submission #313696

#	Time	Username	Problem	Language	Result	Execution time	Memory
313696		tushar_2658	trapezoid (balkan11_trapezoid)	C++14	29 / 100	469 ms	65540 KiB

trapezoid

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

const int maxn = 500005;
using ll = long long;
ll mod = 30013;

struct DATA {
  int l1, r1, l2, r2;
};

DATA p[maxn];
int n;

struct NODE {
  NODE *l, *r;
  int val, sum; 
  NODE(){
    l = nullptr;
    r = nullptr;
    val = sum = 0;
  }
};

NODE *root[maxn];

void build(NODE *cur, int b, int e){
  if(b == e){
    cur -> val = cur -> sum = 0;
    return;
  }
  int mid = (b + e) >> 1;
  if(cur -> l == nullptr)cur -> l = new NODE();
  if(cur -> r == nullptr)cur -> r = new NODE();
  build(cur -> l, b, mid);
  build(cur -> r, mid + 1, e);
}

void upd(NODE *prv, NODE *cur, int b, int e, int idx, pair<int, int> val){
  if(idx > e or idx < b)return;
  if(b == idx && idx == e){
    cur -> val = val.first;
    if(val.second == 0)val.second = 1;
    cur -> sum = val.second;
    return;
  }
  int mid = (b + e) >> 1;
  if(idx <= mid){
    if(cur -> l == nullptr)cur -> l = new NODE();
    cur -> r = prv -> r;
    upd(prv -> l, cur -> l, b, mid, idx, val);
  }else {
    if(cur -> r == nullptr)cur -> r = new NODE();
    cur -> l = prv -> l;
    upd(prv -> r, cur -> r, mid + 1, e, idx, val);
  }
  if(cur -> l == nullptr){
    cur -> val = cur -> r -> val;
    cur -> sum = cur -> r -> sum;
  }else if(cur -> r == nullptr){
    cur -> val = cur -> l -> val;
    cur -> sum = cur -> l -> sum;
  }else if(cur -> l -> val > cur -> r -> val){
    cur -> val = cur -> l -> val;
    cur -> sum = cur -> l -> sum;
  }else if(cur -> l -> val < cur -> r -> val){
    cur -> val = cur -> r -> val;
    cur -> sum = cur -> r -> sum;
  }else {
    cur -> val = cur -> r -> val;
    cur -> sum = (cur -> l -> sum + cur -> r -> sum) % mod;
  }
}

pair<int, int> query(NODE *cur, int b, int e, int i, int j){
  if(i > e or j < b)return make_pair(0, 0);
  if(b >= i && j >= e)return make_pair(cur -> val, cur -> sum);
  int mid = (b + e) >> 1;
  pair<int, int> p1, p2;
  p1 = query(cur -> l, b, mid, i, j);
  p2 = query(cur -> r, mid + 1, e, i, j);
  pair<int, int> ret;
  if(p1.first > p2.first)ret = p1;
  else if(p1.first < p2.first)ret = p2;
  else {
    ret.first = p1.first;
    ret.second = (p1.second + p2.second) % mod;
  }
  return ret;
}

int main(int argc, char const *argv[])
{
  scanf("%d", &n);
  map<int, int> mp;
  for(int i = 1; i <= n; ++i){
    scanf("%d %d %d %d", &p[i].l1, &p[i].r1, &p[i].l2, &p[i].r2);
    mp[p[i].l1];
    mp[p[i].r1];
    mp[p[i].l2];
    mp[p[i].r2];
  }
  int cnt = 0;
  for(auto& i : mp){
    i.second = ++cnt;
  }
  for(int i = 1; i <= n; ++i){
    p[i].l1 = mp[p[i].l1];
    p[i].r1 = mp[p[i].r1];
    p[i].l2 = mp[p[i].l2];
    p[i].r2 = mp[p[i].r2];
  }
  sort(p + 1, p + n + 1, [&](DATA x, DATA y){
    if(x.r1 == y.r1)return x.l1 < y.l1;
    else return x.r1 < y.r1;
  });
  root[0] = new NODE();
  build(root[0], 1, cnt);
  int ans = 1, ans1 = 1;
  root[1] = new NODE();
  upd(root[0], root[1], 1, cnt, p[1].r2, make_pair(1, 1));
  for(int i = 2; i <= n; ++i){
    int lo = 1, hi = i - 1, res = 1; 
    while(lo <= hi){
      int mid = (lo + hi) >> 1;
      if(p[mid].r1 < p[i].l1){
        res = mid;
        lo = mid + 1;
      }else {
        hi = mid - 1;
      }
    }
    pair<int, int> ret = query(root[res], 1, cnt, 1, p[i].l2 - 1);
    if(ret.first + 1 > ans){
      ans = ret.first + 1;
      ans1 = ret.second;
    }
    root[i] = new NODE();
    upd(root[i - 1], root[i], 1, cnt, p[i].r2, make_pair(ret.first + 1, ret.second));
  }
  cout << ans << ' ' << ans1 << endl;

  return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main(int, const char**)':
trapezoid.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
trapezoid.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |     scanf("%d %d %d %d", &p[i].l1, &p[i].r1, &p[i].l2, &p[i].r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 29 / 100