oj.uz

Submission #126842

# Submission time Handle Problem Language Result Execution time Memory
126842 2019-07-08T13:59:54 Z Mohammad_Yasser Examination (JOI19_examination) C++14
41 / 100
 2262 ms 122872 KB 
#ifndef Local
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
typedef long long Long;
typedef pair<int, int> pi;

const int N = 1e5 + 5;

map<int, int> mp_x, mp_y;

template<class T> using Tree = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

void compress() {
  int curr = 0;
  for (auto& p : mp_x) {
    p.second = ++curr;
  }
  curr = 0;
  for (auto& p : mp_y) {
    p.second = ++curr;
  }
}

template<int SZ> struct mstree {
  Tree<pi> val[SZ + 1]; // for offline queries use vector with binary search instead

  void upd(int x, int y, int t = 1) { // x-coordinate between 1 and SZ inclusive
    for (int X = x; X <= SZ; X += X & -X) {
      if (t == 1)
        val[X].insert( { y, x });
      else
        val[X].erase( { y, x });
    }
  }

  int query(int x, int y) {
    int t = 0;
    for (; x > 0; x -= x & -x)
      t += val[x].order_of_key( { y, N });
    return t;
  }

  int query(int lox, int hix, int loy, int hiy) { // query number of elements within a rectangle
    return query(hix, hiy) - query(lox - 1, hiy) - query(hix, loy - 1)
      + query(lox - 1, loy - 1);
  }
};

mstree<N> bit;

struct Score {
  int x, y;
  int sum;

  bool operator<(const Score& other) const {
    return sum < other.sum;
  }
};

struct Query {
  int x, y, z;
  int ind;
  int res;
  bool operator<(const Query& other) const {
    return z < other.z;
  }
};

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

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

  vector<Score> scores(n);
  vector<Query> queries(q);

  for (auto& score : scores) {
    cin >> score.x >> score.y;
    score.sum = score.x + score.y;

    mp_x[score.x];
    mp_y[score.y];
  }
  mp_x[N] , mp_y[N];

  for (int i = 0; i < q; ++i) {
    auto& query = queries[i];
    cin >> query.x >> query.y >> query.z;
    query.ind = i;
  }

  compress();

  for (auto& score : scores) {
    score.x = mp_x[score.x];
    score.y = mp_y[score.y];
  }


  for (auto& query : queries) {
    query.x = mp_x.lower_bound(query.x)->second;
    query.y = mp_y.lower_bound(query.y)->second;
  }

  sort(scores.begin(), scores.end());
  sort(queries.rbegin(), queries.rend());

  for (auto& query : queries) {
    while (!scores.empty() && scores.back().sum >= query.z) {
      bit.upd(scores.back().x, scores.back().y);
      scores.pop_back();
    }
    query.res = bit.query(query.x, N, query.y, N);
  }

  sort(queries.begin(), queries.end(), [](const Query& a , const Query& b) {
    return a.ind < b.ind;
  });

  for (auto& query : queries) {
    cout << query.res << endl;
  }

}

Compilation message

examination.cpp:5:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1024000000,1024000000")

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9720 KB Output is correct
2 Correct 14 ms 9720 KB Output is correct
3 Correct 14 ms 9720 KB Output is correct
4 Correct 16 ms 9720 KB Output is correct
5 Incorrect 14 ms 9720 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2262 ms 76464 KB Output is correct
2 Correct 2170 ms 76316 KB Output is correct
3 Correct 2162 ms 76308 KB Output is correct
4 Correct 1465 ms 73580 KB Output is correct
5 Correct 1482 ms 113400 KB Output is correct
6 Correct 1232 ms 110200 KB Output is correct
7 Correct 1585 ms 76664 KB Output is correct
8 Correct 1959 ms 76336 KB Output is correct
9 Correct 1599 ms 76520 KB Output is correct
10 Correct 1214 ms 122872 KB Output is correct
11 Correct 1037 ms 73252 KB Output is correct
12 Correct 1792 ms 119772 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2262 ms 76464 KB Output is correct
2 Correct 2170 ms 76316 KB Output is correct
3 Correct 2162 ms 76308 KB Output is correct
4 Correct 1465 ms 73580 KB Output is correct
5 Correct 1482 ms 113400 KB Output is correct
6 Correct 1232 ms 110200 KB Output is correct
7 Correct 1585 ms 76664 KB Output is correct
8 Correct 1959 ms 76336 KB Output is correct
9 Correct 1599 ms 76520 KB Output is correct
10 Correct 1214 ms 122872 KB Output is correct
11 Correct 1037 ms 73252 KB Output is correct
12 Correct 1792 ms 119772 KB Output is correct
13 Correct 1848 ms 76496 KB Output is correct
14 Correct 2071 ms 76320 KB Output is correct
15 Correct 2258 ms 76528 KB Output is correct
16 Correct 1061 ms 73464 KB Output is correct
17 Correct 1495 ms 113272 KB Output is correct
18 Correct 1199 ms 110328 KB Output is correct
19 Correct 1683 ms 76536 KB Output is correct
20 Correct 1929 ms 76472 KB Output is correct
21 Correct 1484 ms 76540 KB Output is correct
22 Correct 1499 ms 122844 KB Output is correct
23 Correct 957 ms 73336 KB Output is correct
24 Correct 1767 ms 119696 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9720 KB Output is correct
2 Correct 14 ms 9720 KB Output is correct
3 Correct 14 ms 9720 KB Output is correct
4 Correct 16 ms 9720 KB Output is correct
5 Incorrect 14 ms 9720 KB Output isn't correct
6 Halted 0 ms 0 KB -