oj.uz

Submission #126818

# Submission time Handle Problem Language Result Execution time Memory
126818 2019-07-08T13:24:07 Z Mohammad_Yasser Examination (JOI19_examination) C++14
0 / 100
 2580 ms 106668 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 = 3e5 + 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 38 ms 28536 KB Output is correct
2 Correct 38 ms 28536 KB Output is correct
3 Correct 38 ms 28536 KB Output is correct
4 Correct 38 ms 28536 KB Output is correct
5 Correct 38 ms 28536 KB Output is correct
6 Correct 38 ms 28536 KB Output is correct
7 Correct 70 ms 31736 KB Output is correct
8 Correct 70 ms 31712 KB Output is correct
9 Correct 69 ms 31864 KB Output is correct
10 Correct 63 ms 31536 KB Output is correct
11 Correct 69 ms 32508 KB Output is correct
12 Incorrect 43 ms 28792 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2580 ms 106544 KB Output is correct
2 Correct 2551 ms 106668 KB Output is correct
3 Correct 2399 ms 106444 KB Output is correct
4 Incorrect 1672 ms 101980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2580 ms 106544 KB Output is correct
2 Correct 2551 ms 106668 KB Output is correct
3 Correct 2399 ms 106444 KB Output is correct
4 Incorrect 1672 ms 101980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 28536 KB Output is correct
2 Correct 38 ms 28536 KB Output is correct
3 Correct 38 ms 28536 KB Output is correct
4 Correct 38 ms 28536 KB Output is correct
5 Correct 38 ms 28536 KB Output is correct
6 Correct 38 ms 28536 KB Output is correct
7 Correct 70 ms 31736 KB Output is correct
8 Correct 70 ms 31712 KB Output is correct
9 Correct 69 ms 31864 KB Output is correct
10 Correct 63 ms 31536 KB Output is correct
11 Correct 69 ms 32508 KB Output is correct
12 Incorrect 43 ms 28792 KB Output isn't correct
13 Halted 0 ms 0 KB -