Submission #313703

#	Time	Username	Problem	Language	Result	Execution time	Memory
313703		tushar_2658	trapezoid (balkan11_trapezoid)	C++14	100 / 100	379 ms	28920 KiB

trapezoid

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

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

struct Data {
  int l1, r1, l2, r2;
};
Data p[maxn];
int n;

struct DATA {
  int val, cnt;
  DATA (int val, int cnt) : val(val), cnt(cnt){}
  DATA(){}
};

DATA t[maxn << 2], dp[maxn];
int state[maxn];

DATA join(DATA l, DATA r){
  DATA ret;
  if(l.val > r.val)ret = l;
  else if(l.val < r.val)ret = r;
  else {
    ret.val = l.val;
    ret.cnt = (l.cnt + r.cnt) % mod;
  }
  return ret;
}

void upd(int node, int b, int e, int idx, DATA val){
  if(idx > e or idx < b)return;
  if(b == idx && idx == e){
    t[node] = val;
    return;
  }
  int mid = (b + e) >> 1;
  if(idx <= mid)upd(2*node, b, mid, idx, val);
  else upd(2*node + 1, mid + 1, e, idx, val);
  t[node] = join(t[2*node], t[2*node + 1]);
}

DATA query(int node, int b, int e, int i, int j){
  if(i > e or j < b)return DATA(0, 0);
  if(b >= i && j >= e)return t[node];
  int mid = (b + e) >> 1;
  return join(query(2*node, b, mid, i, j), query(2*node + 1, mid + 1, e, i, j));
}

int main(int argc, char const *argv[])
{
  scanf("%d", &n);
  map<int, int> mp, mp1;
  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];
    mp1[p[i].l2];
    mp1[p[i].r2];
  }
  int cnt = 0;
  for(auto& i : mp){
    i.second = ++cnt;
  }
  cnt = 0; 
  for(auto& i : mp1){
    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 = mp1[p[i].l2];
    p[i].r2 = mp1[p[i].r2];
  }
  for(int i = 1; i <= n; ++i){
    state[p[i].l1] = i;
    state[p[i].r1] = -i;
  }  
  for(int i = 1; i <= (n << 1); ++i){
    int x = abs(state[i]);
    if(state[i] < 0){
      upd(1, 1, cnt, p[x].r2, dp[x]);
    }else {
      dp[x] = query(1, 1, cnt, 1, p[x].l2 - 1);
      dp[x].val++;
      if(dp[x].val == 1){
        dp[x].cnt = 1;
      }
    }
  }
  DATA ans(0, 0);
  for(int i = 1; i <= n; ++i){
    ans = join(ans, dp[i]);
  }
  cout << ans.val << ' ' << ans.cnt << endl;

  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100