oj.uz

Submission #126827

# Submission time Handle Problem Language Result Execution time Memory
126827 2019-07-08T13:39:54 Z Mohammad_Yasser Examination (JOI19_examination) C++14
2 / 100
 3000 ms 69580 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) {
    assert(x >= 0 && y >= 0);
    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;
  }

  while (q--) {
    int x , y , z;
    cin >> x >> y >> z;
    int res = 0;
    for (auto& score : scores) {
      if (score.x >= x && score.y >= y && score.sum >= z) {
        ++res;
      }
    }
    cout << res << endl;
  }

}

Compilation message

examination.cpp:5:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1024000000,1024000000")

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 66040 KB Output is correct
2 Correct 87 ms 66296 KB Output is correct
3 Correct 96 ms 66168 KB Output is correct
4 Correct 85 ms 66040 KB Output is correct
5 Correct 85 ms 66040 KB Output is correct
6 Correct 89 ms 66168 KB Output is correct
7 Correct 100 ms 66168 KB Output is correct
8 Correct 101 ms 66368 KB Output is correct
9 Correct 102 ms 66168 KB Output is correct
10 Correct 99 ms 66268 KB Output is correct
11 Correct 99 ms 66168 KB Output is correct
12 Correct 99 ms 66296 KB Output is correct
13 Correct 99 ms 66296 KB Output is correct
14 Correct 99 ms 66396 KB Output is correct
15 Correct 100 ms 66296 KB Output is correct
16 Correct 100 ms 66252 KB Output is correct
17 Correct 100 ms 66296 KB Output is correct
18 Correct 99 ms 66296 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3033 ms 69580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3033 ms 69580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 66040 KB Output is correct
2 Correct 87 ms 66296 KB Output is correct
3 Correct 96 ms 66168 KB Output is correct
4 Correct 85 ms 66040 KB Output is correct
5 Correct 85 ms 66040 KB Output is correct
6 Correct 89 ms 66168 KB Output is correct
7 Correct 100 ms 66168 KB Output is correct
8 Correct 101 ms 66368 KB Output is correct
9 Correct 102 ms 66168 KB Output is correct
10 Correct 99 ms 66268 KB Output is correct
11 Correct 99 ms 66168 KB Output is correct
12 Correct 99 ms 66296 KB Output is correct
13 Correct 99 ms 66296 KB Output is correct
14 Correct 99 ms 66396 KB Output is correct
15 Correct 100 ms 66296 KB Output is correct
16 Correct 100 ms 66252 KB Output is correct
17 Correct 100 ms 66296 KB Output is correct
18 Correct 99 ms 66296 KB Output is correct
19 Execution timed out 3033 ms 69580 KB Time limit exceeded
20 Halted 0 ms 0 KB -