oj.uz

Submission #261198

# Submission time Handle Problem Language Result Execution time Memory
261198 2020-08-11T14:13:34 Z Bruteforceman Examination (JOI19_examination) C++11
2 / 100
 3000 ms 195720 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int maxn = 2e5 + 10;
typedef pair <int, int> pii;
typedef tree <pii,
              null_type,
              less <pii>,
              rb_tree_tag,
              tree_order_statistics_node_update> orderset;
struct info {
  int x, y, z;
  int id;
  info (int x, int y, int z) : x(x), y(y), z(z) {}
  info () {}
  bool operator < (info d) const {
    if(z == d.z) {
      return id < d.id;
    } 
    return z > d.z;
  }
} a[maxn];

orderset t[maxn * 4];
int ans[maxn];
int idx;
void add(int x, int y, int id, int c = 1, int b = 1, int e = idx) {
  t[c].insert(pii(y, id));
  if(b == e) return ;
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) add(x, y, id, l, b, m);
  else add(x, y, id, r, m + 1, e);
}
int query(int x, int y, int val, int c = 1, int b = 1, int e = idx) {
  if(x <= b && e <= y) {
    return t[c].size() - t[c].order_of_key(pii(val, -1));
  }
  if(y < b || e < x) return 0;
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return query(x, y, val, l, b, m) + query(x, y, val, r, m + 1, e);
}

int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  map <int, int> cmp;
  for(int i = 1; i <= n; i++) {
    scanf("%d %d", &a[i].x, &a[i].y);
    a[i].z = a[i].x + a[i].y;
    a[i].id = i;
    cmp[a[i].x];
  }
  for(int i = n + 1; i <= n + q; i++) {
    scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
    cmp[a[i].x];
    a[i].id = i;
  }
  sort(a + 1, a + n + q + 1);
  idx = 0;
  for(auto &i : cmp) {
    i.second = ++idx;
  }
  for(int i = 1; i <= n + q; i++) {
    a[i].x = cmp[a[i].x];
  }
  for(int i = 1; i <= n + q; i++) {
    if(a[i].id > n) {
      ans[a[i].id - n] = query(a[i].x, idx, a[i].y);
    } else {
      add(a[i].x, a[i].y, a[i].id);
    }
  }
  for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a[i].x, &a[i].y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 75512 KB Output is correct
2 Correct 85 ms 75512 KB Output is correct
3 Correct 81 ms 75640 KB Output is correct
4 Correct 78 ms 75584 KB Output is correct
5 Correct 74 ms 75536 KB Output is correct
6 Correct 77 ms 75512 KB Output is correct
7 Correct 98 ms 78584 KB Output is correct
8 Correct 94 ms 78584 KB Output is correct
9 Correct 91 ms 78584 KB Output is correct
10 Correct 90 ms 78584 KB Output is correct
11 Correct 81 ms 76536 KB Output is correct
12 Correct 81 ms 76536 KB Output is correct
13 Correct 98 ms 78584 KB Output is correct
14 Correct 97 ms 78584 KB Output is correct
15 Correct 98 ms 78584 KB Output is correct
16 Correct 84 ms 76024 KB Output is correct
17 Correct 95 ms 78668 KB Output is correct
18 Correct 83 ms 76152 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 195720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 195720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 75512 KB Output is correct
2 Correct 85 ms 75512 KB Output is correct
3 Correct 81 ms 75640 KB Output is correct
4 Correct 78 ms 75584 KB Output is correct
5 Correct 74 ms 75536 KB Output is correct
6 Correct 77 ms 75512 KB Output is correct
7 Correct 98 ms 78584 KB Output is correct
8 Correct 94 ms 78584 KB Output is correct
9 Correct 91 ms 78584 KB Output is correct
10 Correct 90 ms 78584 KB Output is correct
11 Correct 81 ms 76536 KB Output is correct
12 Correct 81 ms 76536 KB Output is correct
13 Correct 98 ms 78584 KB Output is correct
14 Correct 97 ms 78584 KB Output is correct
15 Correct 98 ms 78584 KB Output is correct
16 Correct 84 ms 76024 KB Output is correct
17 Correct 95 ms 78668 KB Output is correct
18 Correct 83 ms 76152 KB Output is correct
19 Execution timed out 3035 ms 195720 KB Time limit exceeded
20 Halted 0 ms 0 KB -