oj.uz

Submission #329273

# Submission time Handle Problem Language Result Execution time Memory
329273 2020-11-20T04:09:35 Z VROOM_VARUN Examination (JOI19_examination) C++14
43 / 100
 2492 ms 330208 KB 
/*
ID: varunra2
LANG: C++
TASK: exam
*/

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using ordered_set_less = tree<int, null_type, less<int>, rb_tree_tag,
                              tree_order_statistics_node_update>;
using ordered_set_equal = tree<int, null_type, less_equal<int>, rb_tree_tag,
                               tree_order_statistics_node_update>;
using ordered_map =
    tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
const int RANDOM =
    chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
  int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<int, int, chash> table;

// #define int long long

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

const int maxn = 1e5;

const int MAX = maxn + 5;

int cnt = 0;

struct sparsebit {

  vector<gp_hash_table<int, int, chash>> fen;
  int tot = 0;
  void upd(int x, int y, int val) {
    tot++;
    for (int i = x; i <= MAX; i += (i & -i)) {
      for (int j = y; j <= MAX; j += (j & -j)) {
        // debug(i, j, 1);
        // cnt++;
        fen[i][j] += val;
      }
    }
  }

  int qry(int x, int y) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i & -i)) {
      for (int j = y; j > 0; j -= (j & -j)) {
        // cnt++;
        ret += fen[i][j];
      }
    }
    return ret;
  }

  int qry(int a, int b, int c, int d) {
    int ret = 0;
    ret += tot;
    if (a) ret -= qry(a - 1, d);
    if (b) ret -= qry(c, b - 1);
    if (a and b) ret += qry(a - 1, b - 1);
    return ret;
  }

  void init() { fen.resize(MAX + 1); }
};

// MPII comp;
gp_hash_table<int, int, chash> comp[2];

void compress(VI& vals, int ind) {
  // compress math scores then informatics scores seperately
  sort(all(vals));
  vals.resize(unique(all(vals)) - vals.begin());
  for(int i = 0; i < sz(vals); i++) {
    comp[ind][vals[i]] = i + 1;
  }
  // debug(sz(vals));
}

int32_t main() {
  // #ifndef ONLINE_JUDGE
  // freopen("exam.in", "r", stdin);
  // freopen("exam.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  cin >> n >> q;

  VVI vals(n);
  VVI qrys(q);

  VI cmp1, cmp2;

  for (int i = 0; i < n; i++) {
    int s, t;
    cin >> s >> t;
    vals[i] = {s + t, s, t};
    cmp1.PB(s);
    cmp2.PB(t);
  }

  for (int i = 0; i < q; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    qrys[i] = {z, x, y, i};
    cmp1.PB(x);
    cmp2.PB(y);
  }

  compress(cmp1, 0);
  compress(cmp2, 1);

  sort(all(vals));
  sort(all(qrys));

  sparsebit bit;
  bit.init();

  reverse(all(vals));
  reverse(all(qrys));

  int p1 = 0;

  VI ret(q);

  for (int i = 0; i < q; i++) {
    while (p1 < n and vals[p1][0] >= qrys[i][0]) {
      bit.upd(comp[0][vals[p1][1]], comp[1][vals[p1][2]], 1);
      p1++;
    }
    ret[qrys[i][3]] = bit.qry(comp[0][qrys[i][1]], comp[1][qrys[i][2]], MAX, MAX);
  }

  for (int i = 0; i < q; i++) {
    cout << ret[i] << '\n';
  }

  // debug(cnt);

  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 21484 KB Output is correct
2 Correct 27 ms 21484 KB Output is correct
3 Correct 24 ms 21484 KB Output is correct
4 Correct 24 ms 21484 KB Output is correct
5 Correct 24 ms 21484 KB Output is correct
6 Correct 24 ms 21484 KB Output is correct
7 Correct 70 ms 30188 KB Output is correct
8 Correct 68 ms 30188 KB Output is correct
9 Correct 72 ms 31212 KB Output is correct
10 Correct 56 ms 25388 KB Output is correct
11 Correct 43 ms 25264 KB Output is correct
12 Correct 57 ms 21996 KB Output is correct
13 Correct 81 ms 30316 KB Output is correct
14 Correct 69 ms 30316 KB Output is correct
15 Correct 68 ms 30316 KB Output is correct
16 Correct 42 ms 26380 KB Output is correct
17 Correct 52 ms 25516 KB Output is correct
18 Correct 44 ms 21868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 330208 KB Output is correct
2 Correct 2015 ms 328776 KB Output is correct
3 Correct 2033 ms 329448 KB Output is correct
4 Correct 830 ms 95412 KB Output is correct
5 Correct 528 ms 124748 KB Output is correct
6 Correct 607 ms 35540 KB Output is correct
7 Correct 1700 ms 292552 KB Output is correct
8 Correct 1715 ms 288712 KB Output is correct
9 Correct 1697 ms 238188 KB Output is correct
10 Correct 478 ms 120224 KB Output is correct
11 Correct 796 ms 91596 KB Output is correct
12 Correct 603 ms 35144 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 330208 KB Output is correct
2 Correct 2015 ms 328776 KB Output is correct
3 Correct 2033 ms 329448 KB Output is correct
4 Correct 830 ms 95412 KB Output is correct
5 Correct 528 ms 124748 KB Output is correct
6 Correct 607 ms 35540 KB Output is correct
7 Correct 1700 ms 292552 KB Output is correct
8 Correct 1715 ms 288712 KB Output is correct
9 Correct 1697 ms 238188 KB Output is correct
10 Correct 478 ms 120224 KB Output is correct
11 Correct 796 ms 91596 KB Output is correct
12 Correct 603 ms 35144 KB Output is correct
13 Correct 2435 ms 329400 KB Output is correct
14 Correct 2492 ms 329416 KB Output is correct
15 Correct 2059 ms 329124 KB Output is correct
16 Correct 901 ms 97868 KB Output is correct
17 Correct 700 ms 124108 KB Output is correct
18 Correct 677 ms 35668 KB Output is correct
19 Correct 2447 ms 328776 KB Output is correct
20 Correct 2446 ms 328676 KB Output is correct
21 Correct 2185 ms 305096 KB Output is correct
22 Correct 473 ms 119968 KB Output is correct
23 Correct 736 ms 91084 KB Output is correct
24 Correct 699 ms 35284 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 21484 KB Output is correct
2 Correct 27 ms 21484 KB Output is correct
3 Correct 24 ms 21484 KB Output is correct
4 Correct 24 ms 21484 KB Output is correct
5 Correct 24 ms 21484 KB Output is correct
6 Correct 24 ms 21484 KB Output is correct
7 Correct 70 ms 30188 KB Output is correct
8 Correct 68 ms 30188 KB Output is correct
9 Correct 72 ms 31212 KB Output is correct
10 Correct 56 ms 25388 KB Output is correct
11 Correct 43 ms 25264 KB Output is correct
12 Correct 57 ms 21996 KB Output is correct
13 Correct 81 ms 30316 KB Output is correct
14 Correct 69 ms 30316 KB Output is correct
15 Correct 68 ms 30316 KB Output is correct
16 Correct 42 ms 26380 KB Output is correct
17 Correct 52 ms 25516 KB Output is correct
18 Correct 44 ms 21868 KB Output is correct
19 Correct 2011 ms 330208 KB Output is correct
20 Correct 2015 ms 328776 KB Output is correct
21 Correct 2033 ms 329448 KB Output is correct
22 Correct 830 ms 95412 KB Output is correct
23 Correct 528 ms 124748 KB Output is correct
24 Correct 607 ms 35540 KB Output is correct
25 Correct 1700 ms 292552 KB Output is correct
26 Correct 1715 ms 288712 KB Output is correct
27 Correct 1697 ms 238188 KB Output is correct
28 Correct 478 ms 120224 KB Output is correct
29 Correct 796 ms 91596 KB Output is correct
30 Correct 603 ms 35144 KB Output is correct
31 Correct 2435 ms 329400 KB Output is correct
32 Correct 2492 ms 329416 KB Output is correct
33 Correct 2059 ms 329124 KB Output is correct
34 Correct 901 ms 97868 KB Output is correct
35 Correct 700 ms 124108 KB Output is correct
36 Correct 677 ms 35668 KB Output is correct
37 Correct 2447 ms 328776 KB Output is correct
38 Correct 2446 ms 328676 KB Output is correct
39 Correct 2185 ms 305096 KB Output is correct
40 Correct 473 ms 119968 KB Output is correct
41 Correct 736 ms 91084 KB Output is correct
42 Correct 699 ms 35284 KB Output is correct
43 Runtime error 251 ms 94768 KB Execution killed with signal 6 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -