Submission #222709

#	Time	Username	Problem	Language	Result	Execution time	Memory
222709		Bruteforceman	trapezoid (balkan11_trapezoid)	C++11	100 / 100	372 ms	28920 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
const int mod = 30013;
struct trapz {
  int a, b, c, d;
} arr[100010];
int n;
int change[2 * 100010];

struct data {
  int val, cnt;
  data (int val, int cnt) : val(val), cnt(cnt) {}
  data ()  {} 
} t[8 * 100010], dp[100010];
data operator + (data p, data q) {
  if(p.val < q.val) return q;
  else if (p.val > q.val) return p;
  else return data(p.val, (p.cnt + q.cnt) % mod);
}

void update(int x, data d, int c = 1, int b = 1, int e = 2 * n) {
  if(b == e) {
    t[c] = d;
    return ;
  }
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) update(x, d, l, b, m);
  else update(x, d, r, m + 1, e);
  t[c] = t[l] + t[r];
}
data query(int x, int y, int c = 1, int b = 1, int e = 2 * n) {
  if(x > y) return data(0, 0);
  if(x <= b && e <= y) return t[c];
  if(y < b || e < x) return data(0, 0);
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return query(x, y, l, b, m) + query(x, y, r, m + 1, e);
}
int main() {
  scanf("%d", &n);
  map <int, int> cmpA, cmpB;
  for(int i = 1; i <= n; i++) {
    scanf("%d %d %d %d", &arr[i].a, &arr[i].b, &arr[i].c, &arr[i].d);
    cmpA[arr[i].a]; cmpA[arr[i].b];
    cmpB[arr[i].c]; cmpB[arr[i].d];
  }
  int idx = 0;
  for(auto &i : cmpA) i.second = ++idx;
  idx = 0;
  for(auto &i : cmpB) i.second = ++idx;
  for(int i = 1; i <= n; i++) {
    arr[i].a = cmpA[arr[i].a];
    arr[i].b = cmpA[arr[i].b];
    arr[i].c = cmpB[arr[i].c];
    arr[i].d = cmpB[arr[i].d];
  }
  for(int i = 1; i <= n; i++) {
    change[arr[i].a] = i;
    change[arr[i].b] = -i;
  }
  for(int i = 1; i <= 2 * n; i++) {
    int x = abs(change[i]);
    if(change[i] < 0) {
      update(arr[x].d, dp[x]);
    } else if (change[i] > 0) {
      dp[x] = query(1, arr[x].c - 1);
      dp[x].val += 1;
      if(dp[x].val == 1) dp[x].cnt = 1;
    }
  }
  data ans (0, 0);
  for(int i = 1; i <= n; i++) {
    ans = ans + dp[i];
  }
  printf("%d %d\n", ans.val, ans.cnt);
  return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
trapezoid.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &arr[i].a, &arr[i].b, &arr[i].c, &arr[i].d);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100