oj.uz

Submission #126846

# Submission time Handle Problem Language Result Execution time Memory
126846 2019-07-08T14:02:52 Z Mohammad_Yasser Examination (JOI19_examination) C++14
100 / 100
 2199 ms 126316 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[INT_MAX] , mp_y[INT_MAX];

  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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9720 KB Output is correct
2 Correct 14 ms 9848 KB Output is correct
3 Correct 14 ms 9720 KB Output is correct
4 Correct 14 ms 9720 KB Output is correct
5 Correct 14 ms 9720 KB Output is correct
6 Correct 14 ms 9848 KB Output is correct
7 Correct 36 ms 12280 KB Output is correct
8 Correct 36 ms 12280 KB Output is correct
9 Correct 35 ms 12280 KB Output is correct
10 Correct 31 ms 12152 KB Output is correct
11 Correct 36 ms 12920 KB Output is correct
12 Correct 34 ms 12792 KB Output is correct
13 Correct 42 ms 12284 KB Output is correct
14 Correct 37 ms 12280 KB Output is correct
15 Correct 36 ms 12280 KB Output is correct
16 Correct 41 ms 13176 KB Output is correct
17 Correct 30 ms 12152 KB Output is correct
18 Correct 37 ms 13048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2021 ms 76620 KB Output is correct
2 Correct 2069 ms 76380 KB Output is correct
3 Correct 2059 ms 76396 KB Output is correct
4 Correct 1431 ms 73592 KB Output is correct
5 Correct 1434 ms 113404 KB Output is correct
6 Correct 1208 ms 110328 KB Output is correct
7 Correct 1511 ms 76536 KB Output is correct
8 Correct 1889 ms 76508 KB Output is correct
9 Correct 1462 ms 76536 KB Output is correct
10 Correct 1176 ms 122744 KB Output is correct
11 Correct 995 ms 73148 KB Output is correct
12 Correct 1793 ms 119544 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2021 ms 76620 KB Output is correct
2 Correct 2069 ms 76380 KB Output is correct
3 Correct 2059 ms 76396 KB Output is correct
4 Correct 1431 ms 73592 KB Output is correct
5 Correct 1434 ms 113404 KB Output is correct
6 Correct 1208 ms 110328 KB Output is correct
7 Correct 1511 ms 76536 KB Output is correct
8 Correct 1889 ms 76508 KB Output is correct
9 Correct 1462 ms 76536 KB Output is correct
10 Correct 1176 ms 122744 KB Output is correct
11 Correct 995 ms 73148 KB Output is correct
12 Correct 1793 ms 119544 KB Output is correct
13 Correct 1923 ms 76456 KB Output is correct
14 Correct 2057 ms 76520 KB Output is correct
15 Correct 1988 ms 76480 KB Output is correct
16 Correct 1067 ms 73496 KB Output is correct
17 Correct 1508 ms 113312 KB Output is correct
18 Correct 1195 ms 110332 KB Output is correct
19 Correct 1705 ms 76484 KB Output is correct
20 Correct 1894 ms 76592 KB Output is correct
21 Correct 1449 ms 76536 KB Output is correct
22 Correct 1463 ms 122872 KB Output is correct
23 Correct 950 ms 73328 KB Output is correct
24 Correct 1822 ms 119676 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9720 KB Output is correct
2 Correct 14 ms 9848 KB Output is correct
3 Correct 14 ms 9720 KB Output is correct
4 Correct 14 ms 9720 KB Output is correct
5 Correct 14 ms 9720 KB Output is correct
6 Correct 14 ms 9848 KB Output is correct
7 Correct 36 ms 12280 KB Output is correct
8 Correct 36 ms 12280 KB Output is correct
9 Correct 35 ms 12280 KB Output is correct
10 Correct 31 ms 12152 KB Output is correct
11 Correct 36 ms 12920 KB Output is correct
12 Correct 34 ms 12792 KB Output is correct
13 Correct 42 ms 12284 KB Output is correct
14 Correct 37 ms 12280 KB Output is correct
15 Correct 36 ms 12280 KB Output is correct
16 Correct 41 ms 13176 KB Output is correct
17 Correct 30 ms 12152 KB Output is correct
18 Correct 37 ms 13048 KB Output is correct
19 Correct 2021 ms 76620 KB Output is correct
20 Correct 2069 ms 76380 KB Output is correct
21 Correct 2059 ms 76396 KB Output is correct
22 Correct 1431 ms 73592 KB Output is correct
23 Correct 1434 ms 113404 KB Output is correct
24 Correct 1208 ms 110328 KB Output is correct
25 Correct 1511 ms 76536 KB Output is correct
26 Correct 1889 ms 76508 KB Output is correct
27 Correct 1462 ms 76536 KB Output is correct
28 Correct 1176 ms 122744 KB Output is correct
29 Correct 995 ms 73148 KB Output is correct
30 Correct 1793 ms 119544 KB Output is correct
31 Correct 1923 ms 76456 KB Output is correct
32 Correct 2057 ms 76520 KB Output is correct
33 Correct 1988 ms 76480 KB Output is correct
34 Correct 1067 ms 73496 KB Output is correct
35 Correct 1508 ms 113312 KB Output is correct
36 Correct 1195 ms 110332 KB Output is correct
37 Correct 1705 ms 76484 KB Output is correct
38 Correct 1894 ms 76592 KB Output is correct
39 Correct 1449 ms 76536 KB Output is correct
40 Correct 1463 ms 122872 KB Output is correct
41 Correct 950 ms 73328 KB Output is correct
42 Correct 1822 ms 119676 KB Output is correct
43 Correct 2001 ms 77860 KB Output is correct
44 Correct 1866 ms 77944 KB Output is correct
45 Correct 2199 ms 77956 KB Output is correct
46 Correct 1186 ms 75104 KB Output is correct
47 Correct 1332 ms 116772 KB Output is correct
48 Correct 1114 ms 111156 KB Output is correct
49 Correct 1805 ms 79676 KB Output is correct
50 Correct 1828 ms 79628 KB Output is correct
51 Correct 1600 ms 79772 KB Output is correct
52 Correct 1739 ms 126316 KB Output is correct
53 Correct 1076 ms 74916 KB Output is correct