oj.uz

Submission #908657

# Submission time Handle Problem Language Result Execution time Memory
908657 2024-01-16T15:58:44 Z duckindog trapezoid (balkan11_trapezoid) C++14
38 / 100
 117 ms 60172 KB 
// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10,
          M = 30013;
struct rec {
  int a = 0, b = 0, c = 0, d = 0;

  bool operator < (const rec& rhs) {
    return make_pair(b, d) < make_pair(rhs.b, rhs.b);
  }
} r[N];
int n;
bool crossed(rec x, rec y) {
  if (min(x.a, x.c) > min(y.a, y.c)) swap(x, y);
  return (x.b >= y.a || x.d >= y.c);
}
vector<int> remind[N];
vector<int> rrh;
using pii = pair<int, int>;
pair<int, int> f[4 * N];
void update(int s, int l, int r, pii x, int y) {
  if (y < l || y > r) return;
  if (l == r) {
    f[s] = max(f[s], x);
    return;
  }
  int mid = l + r >> 1;
  update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
  int ma = max(f[s * 2].first, f[s * 2 + 1].first);
  f[s].first = ma;
  f[s].second = (f[s * 2].second * (f[s * 2].first == ma) + f[s * 2 + 1].second * (f[s * 2 + 1].first == ma)) % M;

}
pii query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return {0, 0};
  if (u <= l && r <= v) return f[s];
  int mid = l + r >> 1;
  auto lt = query(s * 2, l, mid, u, v), rt = query(s * 2 + 1, mid + 1, r, u, v);
  int ma = max(lt.first, rt.first);
  return {ma, (lt.second * (lt.first == ma) + rt.second * (rt.first == ma)) % M};

}

pii dp[N];

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    r[i] = {a, b, c, d};
  }
  sort(r + 1, r + n + 1);

  for (int i = 1; i <= n; ++i) {
    int a = r[i].a, b = r[i].b;
    int lt = 0, rt = i - 1, it = 0;
    while (lt <= rt) {
      int mid = lt + rt >> 1;
      if (r[mid].b <= a) lt = (it = mid) + 1;
      else rt = mid - 1;
    }
    remind[it].push_back(i);

  }


  dp[0] = {0, 1};

  for (int i = 0; i <= n; ++i) {

    update(1, 0, 1e6, dp[i], r[i].d);
    for (auto x : remind[i]) {
      int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      dp[x] = query(1, 0, 1e6, 0, c);
      dp[x].first += 1;
    }

  }
  auto answer = query(1, 0, 1e6, 0, 1e6);
  cout << answer.first << ' ' << 0;

}

Compilation message

trapezoid.cpp: In function 'void update(long long int, long long int, long long int, pii, long long int)':
trapezoid.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid = l + r >> 1;
      |             ~~^~~
trapezoid.cpp: In function 'pii query(long long int, long long int, long long int, long long int, long long int)':
trapezoid.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid = l + r >> 1;
      |             ~~^~~
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:69:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |       int mid = lt + rt >> 1;
      |                 ~~~^~~~
trapezoid.cpp:66:21: warning: unused variable 'b' [-Wunused-variable]
   66 |     int a = r[i].a, b = r[i].b;
      |                     ^
trapezoid.cpp:84:11: warning: unused variable 'a' [-Wunused-variable]
   84 |       int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      |           ^
trapezoid.cpp:84:23: warning: unused variable 'b' [-Wunused-variable]
   84 |       int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      |                       ^
trapezoid.cpp:84:47: warning: unused variable 'd' [-Wunused-variable]
   84 |       int a = r[x].a, b = r[x].b, c = r[x].c, d = r[x].d;
      |                                               ^
trapezoid.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 33112 KB Partially correct
2 Partially correct 10 ms 33116 KB Partially correct
3 Partially correct 10 ms 33116 KB Partially correct
4 Partially correct 11 ms 33372 KB Partially correct
5 Partially correct 11 ms 33628 KB Partially correct
6 Partially correct 13 ms 34652 KB Partially correct
7 Partially correct 12 ms 34396 KB Partially correct
8 Partially correct 14 ms 33628 KB Partially correct
9 Partially correct 19 ms 33880 KB Partially correct
10 Partially correct 37 ms 44880 KB Partially correct
11 Partially correct 40 ms 39764 KB Partially correct
12 Partially correct 69 ms 51440 KB Partially correct
13 Partially correct 84 ms 52660 KB Partially correct
14 Incorrect 80 ms 59728 KB Output isn't correct
15 Partially correct 94 ms 47184 KB Partially correct
16 Partially correct 100 ms 50436 KB Partially correct
17 Partially correct 117 ms 60172 KB Partially correct
18 Partially correct 95 ms 50172 KB Partially correct
19 Partially correct 111 ms 50416 KB Partially correct
20 Partially correct 114 ms 54612 KB Partially correct