oj.uz

답안 #126820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126820 2019-07-08T13:27:11 Z Mohammad_Yasser Examination (JOI19_examination) C++14
0 / 100
 2639 ms 141164 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 = 6e5 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 56696 KB Output is correct
2 Correct 73 ms 56668 KB Output is correct
3 Correct 74 ms 56696 KB Output is correct
4 Correct 74 ms 56828 KB Output is correct
5 Correct 73 ms 56700 KB Output is correct
6 Correct 73 ms 56696 KB Output is correct
7 Correct 107 ms 60152 KB Output is correct
8 Correct 123 ms 60152 KB Output is correct
9 Correct 106 ms 60240 KB Output is correct
10 Correct 100 ms 59896 KB Output is correct
11 Correct 107 ms 60920 KB Output is correct
12 Incorrect 80 ms 56952 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2581 ms 141000 KB Output is correct
2 Correct 2639 ms 141164 KB Output is correct
3 Correct 2598 ms 141132 KB Output is correct
4 Incorrect 1826 ms 136252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2581 ms 141000 KB Output is correct
2 Correct 2639 ms 141164 KB Output is correct
3 Correct 2598 ms 141132 KB Output is correct
4 Incorrect 1826 ms 136252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 56696 KB Output is correct
2 Correct 73 ms 56668 KB Output is correct
3 Correct 74 ms 56696 KB Output is correct
4 Correct 74 ms 56828 KB Output is correct
5 Correct 73 ms 56700 KB Output is correct
6 Correct 73 ms 56696 KB Output is correct
7 Correct 107 ms 60152 KB Output is correct
8 Correct 123 ms 60152 KB Output is correct
9 Correct 106 ms 60240 KB Output is correct
10 Correct 100 ms 59896 KB Output is correct
11 Correct 107 ms 60920 KB Output is correct
12 Incorrect 80 ms 56952 KB Output isn't correct
13 Halted 0 ms 0 KB -