oj.uz

Submission #126833

# Submission time Handle Problem Language Result Execution time Memory
126833 2019-07-08T13:53:08 Z Mohammad_Yasser Examination (JOI19_examination) C++14
0 / 100
 2462 ms 154104 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_equal<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;
    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.lower_bound(query.x)->second;
    query.y = mp.lower_bound(query.y)->second;
    query.z = mp.lower_bound(query.z)->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 Incorrect 38 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2348 ms 107064 KB Output is correct
2 Correct 2462 ms 106884 KB Output is correct
3 Correct 2314 ms 107092 KB Output is correct
4 Correct 1557 ms 105464 KB Output is correct
5 Correct 1674 ms 145720 KB Output is correct
6 Correct 1467 ms 141664 KB Output is correct
7 Correct 1858 ms 107100 KB Output is correct
8 Correct 2421 ms 107000 KB Output is correct
9 Correct 1664 ms 107000 KB Output is correct
10 Incorrect 1374 ms 154104 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2348 ms 107064 KB Output is correct
2 Correct 2462 ms 106884 KB Output is correct
3 Correct 2314 ms 107092 KB Output is correct
4 Correct 1557 ms 105464 KB Output is correct
5 Correct 1674 ms 145720 KB Output is correct
6 Correct 1467 ms 141664 KB Output is correct
7 Correct 1858 ms 107100 KB Output is correct
8 Correct 2421 ms 107000 KB Output is correct
9 Correct 1664 ms 107000 KB Output is correct
10 Incorrect 1374 ms 154104 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 28536 KB Output isn't correct
2 Halted 0 ms 0 KB -