oj.uz

Submission #126817

# Submission time Handle Problem Language Result Execution time Memory
126817 2019-07-08T13:22:33 Z Mohammad_Yasser Examination (JOI19_examination) C++14
0 / 100
 2403 ms 91220 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 = 2e5 + 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;
  }
}

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 27 ms 19064 KB Output is correct
2 Correct 26 ms 19064 KB Output is correct
3 Correct 27 ms 19064 KB Output is correct
4 Correct 31 ms 19064 KB Output is correct
5 Correct 26 ms 19320 KB Output is correct
6 Correct 26 ms 19192 KB Output is correct
7 Correct 55 ms 22264 KB Output is correct
8 Correct 58 ms 22264 KB Output is correct
9 Correct 58 ms 22236 KB Output is correct
10 Correct 51 ms 22008 KB Output is correct
11 Correct 56 ms 22904 KB Output is correct
12 Incorrect 31 ms 19320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2403 ms 91008 KB Output is correct
2 Correct 2344 ms 91220 KB Output is correct
3 Correct 2325 ms 91052 KB Output is correct
4 Incorrect 1632 ms 86964 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2403 ms 91008 KB Output is correct
2 Correct 2344 ms 91220 KB Output is correct
3 Correct 2325 ms 91052 KB Output is correct
4 Incorrect 1632 ms 86964 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19064 KB Output is correct
2 Correct 26 ms 19064 KB Output is correct
3 Correct 27 ms 19064 KB Output is correct
4 Correct 31 ms 19064 KB Output is correct
5 Correct 26 ms 19320 KB Output is correct
6 Correct 26 ms 19192 KB Output is correct
7 Correct 55 ms 22264 KB Output is correct
8 Correct 58 ms 22264 KB Output is correct
9 Correct 58 ms 22236 KB Output is correct
10 Correct 51 ms 22008 KB Output is correct
11 Correct 56 ms 22904 KB Output is correct
12 Incorrect 31 ms 19320 KB Output isn't correct
13 Halted 0 ms 0 KB -