oj.uz

Submission #329268

# Submission time Handle Problem Language Result Execution time Memory
329268 2020-11-20T03:31:41 Z VROOM_VARUN Examination (JOI19_examination) C++14
22 / 100
 3000 ms 418568 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 = 4 * maxn + 5;

int cnt = 0;

struct sparsebit {
  vector<gp_hash_table<int, int, chash>> fen;
  void upd(int x, int y, int val) {
    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 += qry(c, d);
    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;

void compress(VI vals) {
  sort(all(vals));
  vals.resize(unique(all(vals)) - vals.begin());
  for (int i = 0; i < sz(vals); i++) {
    comp[vals[i]] = i + 2;
  }
  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 cmp;

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

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

  compress(cmp);

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

  sparsebit bit;
  bit.init();

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

  int p1 = 0;

  VI ret(q, 0);

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

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

  // debug(cnt);

  return 0;
}

Compilation message

examination.cpp: In function 'void compress(VI)':
examination.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
examination.cpp:119:3: note: in expansion of macro 'debug'
  119 |   debug(sz(vals));
      |   ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 84972 KB Output is correct
2 Correct 89 ms 84972 KB Output is correct
3 Correct 87 ms 84972 KB Output is correct
4 Correct 88 ms 84972 KB Output is correct
5 Correct 87 ms 84972 KB Output is correct
6 Correct 87 ms 84992 KB Output is correct
7 Correct 162 ms 97004 KB Output is correct
8 Correct 162 ms 96876 KB Output is correct
9 Correct 164 ms 96768 KB Output is correct
10 Correct 141 ms 89212 KB Output is correct
11 Correct 121 ms 88940 KB Output is correct
12 Correct 126 ms 85356 KB Output is correct
13 Correct 158 ms 97004 KB Output is correct
14 Correct 152 ms 97004 KB Output is correct
15 Correct 156 ms 97004 KB Output is correct
16 Correct 124 ms 88616 KB Output is correct
17 Correct 133 ms 88940 KB Output is correct
18 Correct 131 ms 85228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2798 ms 416100 KB Output is correct
2 Correct 2713 ms 417780 KB Output is correct
3 Correct 2727 ms 418568 KB Output is correct
4 Correct 1335 ms 173776 KB Output is correct
5 Correct 786 ms 192832 KB Output is correct
6 Correct 1099 ms 99520 KB Output is correct
7 Correct 2427 ms 377084 KB Output is correct
8 Correct 2446 ms 376384 KB Output is correct
9 Correct 2148 ms 323312 KB Output is correct
10 Correct 688 ms 188504 KB Output is correct
11 Correct 1192 ms 156652 KB Output is correct
12 Correct 971 ms 99120 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2798 ms 416100 KB Output is correct
2 Correct 2713 ms 417780 KB Output is correct
3 Correct 2727 ms 418568 KB Output is correct
4 Correct 1335 ms 173776 KB Output is correct
5 Correct 786 ms 192832 KB Output is correct
6 Correct 1099 ms 99520 KB Output is correct
7 Correct 2427 ms 377084 KB Output is correct
8 Correct 2446 ms 376384 KB Output is correct
9 Correct 2148 ms 323312 KB Output is correct
10 Correct 688 ms 188504 KB Output is correct
11 Correct 1192 ms 156652 KB Output is correct
12 Correct 971 ms 99120 KB Output is correct
13 Execution timed out 3108 ms 417972 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 84972 KB Output is correct
2 Correct 89 ms 84972 KB Output is correct
3 Correct 87 ms 84972 KB Output is correct
4 Correct 88 ms 84972 KB Output is correct
5 Correct 87 ms 84972 KB Output is correct
6 Correct 87 ms 84992 KB Output is correct
7 Correct 162 ms 97004 KB Output is correct
8 Correct 162 ms 96876 KB Output is correct
9 Correct 164 ms 96768 KB Output is correct
10 Correct 141 ms 89212 KB Output is correct
11 Correct 121 ms 88940 KB Output is correct
12 Correct 126 ms 85356 KB Output is correct
13 Correct 158 ms 97004 KB Output is correct
14 Correct 152 ms 97004 KB Output is correct
15 Correct 156 ms 97004 KB Output is correct
16 Correct 124 ms 88616 KB Output is correct
17 Correct 133 ms 88940 KB Output is correct
18 Correct 131 ms 85228 KB Output is correct
19 Correct 2798 ms 416100 KB Output is correct
20 Correct 2713 ms 417780 KB Output is correct
21 Correct 2727 ms 418568 KB Output is correct
22 Correct 1335 ms 173776 KB Output is correct
23 Correct 786 ms 192832 KB Output is correct
24 Correct 1099 ms 99520 KB Output is correct
25 Correct 2427 ms 377084 KB Output is correct
26 Correct 2446 ms 376384 KB Output is correct
27 Correct 2148 ms 323312 KB Output is correct
28 Correct 688 ms 188504 KB Output is correct
29 Correct 1192 ms 156652 KB Output is correct
30 Correct 971 ms 99120 KB Output is correct
31 Execution timed out 3108 ms 417972 KB Time limit exceeded
32 Halted 0 ms 0 KB -