oj.uz

Submission #529698

# Submission time Handle Problem Language Result Execution time Memory
529698 2022-02-23T13:10:44 Z Alex_tz307 Examination (JOI19_examination) C++17
0 / 100
 296 ms 13388 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
int N, sol[kN], aib[1 + 2 * kN];

struct student {
  int x, y, z, index;
} a[2 * kN];

bool cmp1(const student &lhs, const student &rhs) {
  return lhs.z > rhs.z;
}

bool cmp2(const student &lhs, const student &rhs) {
  if (lhs.x != rhs.x) {
    return lhs.x > rhs.x;
  }
  return lhs.index < rhs.index;
}

void update(int x, int v) {
  for (int i = x; i <= N; i += i & -i) {
    aib[i] += v;
  }
}

int query(int x) {
  int ans = 0;
  for (int i = x; i > 0; i = i & (i - 1)) {
    ans += aib[i];
  }
  return ans;
}

int query(int l, int r) {
  return query(r) - query(l - 1);
}

void solve(int l, int r) {
  if (r <= l) {
    return;
  }
  int mid = (l + r) / 2;
  vector<student> ev;
  for (int i = l; i <= mid; ++i) {
    if (a[i].index == -1) {
      ev.emplace_back(a[i]);
    }
  }
  for (int i = mid + 1; i <= r; ++i) {
    if (a[i].index != -1) {
      ev.emplace_back(a[i]);
    }
  }
  sort(ev.begin(), ev.end(), cmp2);
  vector<int> updates;
  for (auto it : ev) {
    int y = it.y, index = it.index;
    if (index == -1) {
      update(y, 1);
      updates.emplace_back(y);
    } else {
      sol[index] += query(y, N);
    }
  }
  ev.clear();
  for (int y : updates) {
    update(y, -1);
  }
  updates.clear();
  solve(l, mid);
  solve(mid + 1, r);
}

void testCase() {
  int n, q;
  cin >> n >> q;
  vector<int> ys(n + q);
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    a[i] = {x, y, x + y, -1};
    ys[i] = y;
  }
  for (int i = 0; i < q; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    a[n + i] = {x, y, z, i};
    ys[n + i] = y;
  }
  int m = n + q;
  sort(a, a + m, cmp1);
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  N = ys.size();
  for (int i = 0; i < m; ++i) {
    a[i].y = distance(ys.begin(), upper_bound(ys.begin(), ys.end(), a[i].y));
  }
  ys.clear();
  solve(0, m - 1);
  for (int i = 0; i < q; ++i) {
    cout << sol[i] << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 7 ms 700 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 8 ms 748 KB Output is correct
10 Correct 5 ms 712 KB Output is correct
11 Correct 7 ms 732 KB Output is correct
12 Incorrect 5 ms 588 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 13364 KB Output is correct
2 Correct 296 ms 13388 KB Output is correct
3 Correct 272 ms 13328 KB Output is correct
4 Correct 196 ms 12344 KB Output is correct
5 Correct 250 ms 12668 KB Output is correct
6 Incorrect 183 ms 11624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 13364 KB Output is correct
2 Correct 296 ms 13388 KB Output is correct
3 Correct 272 ms 13328 KB Output is correct
4 Correct 196 ms 12344 KB Output is correct
5 Correct 250 ms 12668 KB Output is correct
6 Incorrect 183 ms 11624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 7 ms 700 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 8 ms 748 KB Output is correct
10 Correct 5 ms 712 KB Output is correct
11 Correct 7 ms 732 KB Output is correct
12 Incorrect 5 ms 588 KB Output isn't correct
13 Halted 0 ms 0 KB -