oj.uz

Submission #752045

# Submission time Handle Problem Language Result Execution time Memory
752045 2023-06-02T07:59:24 Z NeroZein Examination (JOI19_examination) C++17
100 / 100
 1295 ms 95468 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;
 
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
 
const int N = 100005;
 
template <class T> using Tree = tree<T,null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
Tree<int> tr[N]; 
 
void upd (int id, int v) {
  id++; 
  while (id < N) {
    tr[id].insert(v); 
    id += id & -id; 
  }
}
 
int qry (int id, int v) {
  id++; 
  int ret = 0; 
  while (id) {
    ret += tr[id].size() - tr[id].order_of_key(v);
    id -= id & -id;
  }
  return ret;
}
 
int qry (int l, int r, int v) {
  return qry(r, v) - qry(l - 1, v); 
}
 
struct St {
  int a, b, c, id;
  bool operator < (const St& other) {
    return c > other.c; 
  }; 
}; 
 
int a[N]; 
St s[N], qs[N]; 
int ans[N]; 
 
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    cin >> s[i].a >> s[i].b;
    s[i].c = s[i].a + s[i].b; 
    a[i] = s[i].a;
  }
  sort(a, a + n); 
  sort(s, s + n); 
  for (int i = 0; i < n; ++i) {
    s[i].a = lower_bound(a, a + n, s[i].a) - a; 
  }
  for (int i = 0; i < q; ++i) {
    cin >> qs[i].a >> qs[i].b >> qs[i].c;
    qs[i].id = i;
    qs[i].a = lower_bound(a, a + n, qs[i].a) - a; 
  }
  sort(qs, qs + q); 
  for (int i = 0, p = 0; i < q; ++i) {
    while (p < n && s[p].c >= qs[i].c) {
      upd(s[p].a, s[p].b); 
      p++; 
    }
    ans[qs[i].id] = qry(qs[i].a, n - 1, qs[i].b);
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n'; 
  }
  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8148 KB Output is correct
2 Correct 7 ms 8148 KB Output is correct
3 Correct 8 ms 8188 KB Output is correct
4 Correct 7 ms 8164 KB Output is correct
5 Correct 10 ms 8080 KB Output is correct
6 Correct 7 ms 8148 KB Output is correct
7 Correct 22 ms 9980 KB Output is correct
8 Correct 20 ms 9996 KB Output is correct
9 Correct 20 ms 9940 KB Output is correct
10 Correct 18 ms 9940 KB Output is correct
11 Correct 18 ms 10068 KB Output is correct
12 Correct 16 ms 9940 KB Output is correct
13 Correct 19 ms 9996 KB Output is correct
14 Correct 21 ms 10012 KB Output is correct
15 Correct 20 ms 9960 KB Output is correct
16 Correct 21 ms 10708 KB Output is correct
17 Correct 18 ms 9944 KB Output is correct
18 Correct 26 ms 10676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1225 ms 54036 KB Output is correct
2 Correct 1284 ms 56276 KB Output is correct
3 Correct 1231 ms 56240 KB Output is correct
4 Correct 755 ms 55528 KB Output is correct
5 Correct 578 ms 59564 KB Output is correct
6 Correct 467 ms 60656 KB Output is correct
7 Correct 902 ms 56312 KB Output is correct
8 Correct 972 ms 56196 KB Output is correct
9 Correct 674 ms 56152 KB Output is correct
10 Correct 715 ms 93992 KB Output is correct
11 Correct 544 ms 55308 KB Output is correct
12 Correct 929 ms 93128 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1225 ms 54036 KB Output is correct
2 Correct 1284 ms 56276 KB Output is correct
3 Correct 1231 ms 56240 KB Output is correct
4 Correct 755 ms 55528 KB Output is correct
5 Correct 578 ms 59564 KB Output is correct
6 Correct 467 ms 60656 KB Output is correct
7 Correct 902 ms 56312 KB Output is correct
8 Correct 972 ms 56196 KB Output is correct
9 Correct 674 ms 56152 KB Output is correct
10 Correct 715 ms 93992 KB Output is correct
11 Correct 544 ms 55308 KB Output is correct
12 Correct 929 ms 93128 KB Output is correct
13 Correct 1022 ms 56728 KB Output is correct
14 Correct 1206 ms 56672 KB Output is correct
15 Correct 1187 ms 56312 KB Output is correct
16 Correct 576 ms 55968 KB Output is correct
17 Correct 489 ms 56552 KB Output is correct
18 Correct 459 ms 57548 KB Output is correct
19 Correct 948 ms 56700 KB Output is correct
20 Correct 1056 ms 56728 KB Output is correct
21 Correct 809 ms 56812 KB Output is correct
22 Correct 715 ms 94068 KB Output is correct
23 Correct 503 ms 55420 KB Output is correct
24 Correct 962 ms 93004 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8148 KB Output is correct
2 Correct 7 ms 8148 KB Output is correct
3 Correct 8 ms 8188 KB Output is correct
4 Correct 7 ms 8164 KB Output is correct
5 Correct 10 ms 8080 KB Output is correct
6 Correct 7 ms 8148 KB Output is correct
7 Correct 22 ms 9980 KB Output is correct
8 Correct 20 ms 9996 KB Output is correct
9 Correct 20 ms 9940 KB Output is correct
10 Correct 18 ms 9940 KB Output is correct
11 Correct 18 ms 10068 KB Output is correct
12 Correct 16 ms 9940 KB Output is correct
13 Correct 19 ms 9996 KB Output is correct
14 Correct 21 ms 10012 KB Output is correct
15 Correct 20 ms 9960 KB Output is correct
16 Correct 21 ms 10708 KB Output is correct
17 Correct 18 ms 9944 KB Output is correct
18 Correct 26 ms 10676 KB Output is correct
19 Correct 1225 ms 54036 KB Output is correct
20 Correct 1284 ms 56276 KB Output is correct
21 Correct 1231 ms 56240 KB Output is correct
22 Correct 755 ms 55528 KB Output is correct
23 Correct 578 ms 59564 KB Output is correct
24 Correct 467 ms 60656 KB Output is correct
25 Correct 902 ms 56312 KB Output is correct
26 Correct 972 ms 56196 KB Output is correct
27 Correct 674 ms 56152 KB Output is correct
28 Correct 715 ms 93992 KB Output is correct
29 Correct 544 ms 55308 KB Output is correct
30 Correct 929 ms 93128 KB Output is correct
31 Correct 1022 ms 56728 KB Output is correct
32 Correct 1206 ms 56672 KB Output is correct
33 Correct 1187 ms 56312 KB Output is correct
34 Correct 576 ms 55968 KB Output is correct
35 Correct 489 ms 56552 KB Output is correct
36 Correct 459 ms 57548 KB Output is correct
37 Correct 948 ms 56700 KB Output is correct
38 Correct 1056 ms 56728 KB Output is correct
39 Correct 809 ms 56812 KB Output is correct
40 Correct 715 ms 94068 KB Output is correct
41 Correct 503 ms 55420 KB Output is correct
42 Correct 962 ms 93004 KB Output is correct
43 Correct 1033 ms 57744 KB Output is correct
44 Correct 1020 ms 57624 KB Output is correct
45 Correct 1295 ms 57656 KB Output is correct
46 Correct 635 ms 57136 KB Output is correct
47 Correct 503 ms 58228 KB Output is correct
48 Correct 409 ms 58676 KB Output is correct
49 Correct 871 ms 57700 KB Output is correct
50 Correct 795 ms 57676 KB Output is correct
51 Correct 707 ms 57676 KB Output is correct
52 Correct 955 ms 95468 KB Output is correct
53 Correct 623 ms 56136 KB Output is correct