oj.uz

Submission #126821

# Submission time Handle Problem Language Result Execution time Memory
126821 2019-07-08T13:28:04 Z Mohammad_Yasser Examination (JOI19_examination) C++14
0 / 100
 2979 ms 152384 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 = 7e5 + 5;

map<int, int> mp;

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

void compress() {
  int curr = 0;
  for (auto& p : mp) {
    p.second = ++curr;
  }
  assert(curr < N);
}

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[score.x];
    mp[score.y];
    mp[score.sum];
  }

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

    query.ind = i;
  }

  compress();

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


  for (auto& query : queries) {
    query.x = mp[query.x];
    query.y = mp[query.y];
    query.z = mp[query.z];
  }


  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 86 ms 66048 KB Output is correct
2 Correct 86 ms 66160 KB Output is correct
3 Correct 87 ms 66148 KB Output is correct
4 Correct 85 ms 66024 KB Output is correct
5 Correct 86 ms 66040 KB Output is correct
6 Correct 85 ms 66040 KB Output is correct
7 Correct 117 ms 69724 KB Output is correct
8 Correct 118 ms 69704 KB Output is correct
9 Correct 119 ms 69760 KB Output is correct
10 Correct 124 ms 69348 KB Output is correct
11 Correct 120 ms 70368 KB Output is correct
12 Incorrect 90 ms 66424 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2653 ms 151340 KB Output is correct
2 Correct 2760 ms 152384 KB Output is correct
3 Correct 2979 ms 152324 KB Output is correct
4 Incorrect 1821 ms 147472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2653 ms 151340 KB Output is correct
2 Correct 2760 ms 152384 KB Output is correct
3 Correct 2979 ms 152324 KB Output is correct
4 Incorrect 1821 ms 147472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 66048 KB Output is correct
2 Correct 86 ms 66160 KB Output is correct
3 Correct 87 ms 66148 KB Output is correct
4 Correct 85 ms 66024 KB Output is correct
5 Correct 86 ms 66040 KB Output is correct
6 Correct 85 ms 66040 KB Output is correct
7 Correct 117 ms 69724 KB Output is correct
8 Correct 118 ms 69704 KB Output is correct
9 Correct 119 ms 69760 KB Output is correct
10 Correct 124 ms 69348 KB Output is correct
11 Correct 120 ms 70368 KB Output is correct
12 Incorrect 90 ms 66424 KB Output isn't correct
13 Halted 0 ms 0 KB -