Submission #261216

#	Time	Username	Problem	Language	Result	Execution time	Memory
261216		Bruteforceman	Examination (JOI19_examination)	C++11	2 / 100	63 ms	5360 KiB

examination

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct info {
  int x, y, z;
  int id;
  info (int x, int y, int z) : x(x), y(y), z(z) {}
  info () {}
  bool operator < (info d) const {
    if(z == d.z) {
      return id < d.id;
    } 
    return z > d.z;
  }
} a[maxn];
int n, idx;
int ans[maxn];
int t[maxn];
void update(int x, int val) {
  for(int i = x; i <= idx; i += i & (-i)) t[i] += val;
}
int query(int x) {
  int sum = 0;
  for(int i = x; i > 0; i -= i & (-i)) {
    sum += t[i];
  }
  return sum;
}
void solve(int l, int r) {
  if(l == r) return ;
  int m = (l + r) >> 1;
  solve(l, m);
  solve(m + 1, r);
  vector <int> cont;
  for(int i = l; i <= m; i++) {
    if(a[i].id <= n) cont.emplace_back(i);
  }
  for(int i = m + 1; i <= r; i++) {
    if(a[i].id > n) cont.emplace_back(i);
  }
  sort(cont.begin(), cont.end(), 
    [&] (int i, int j) {
      if(a[i].y == a[j].y) return i < j;
      else return a[i].y > a[j].y; 
    }
  );
  for(auto i : cont) {
    if(a[i].id <= n) {
      update(a[i].x, 1);
    } else {
      ans[a[i].id] += query(idx) - query(a[i].x - 1);
    } 
  }
  for(auto i : cont) {
    if(a[i].id <= n) {
      update(a[i].x, -1);
    }
  }
}

int main() {
  int q;
  scanf("%d %d", &n, &q);
  map <int, int> cmp;
  vector <int> v;
  cmp[INT_MAX];
  v.push_back(INT_MAX);
  for(int i = 1; i <= n; i++) {
    scanf("%d %d", &a[i].x, &a[i].y);
    a[i].z = a[i].x + a[i].y;
    a[i].id = i;
    cmp[a[i].x];
    v.push_back(a[i].x);
  }
  for(int i = n + 1; i <= n + q; i++) {
    scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
    a[i].id = i;
  }
  sort(a + 1, a + n + q + 1);
  idx = 0;
  for(auto &i : cmp) {
    i.second = ++idx;
  }
  sort(v.begin(), v.end());
  for(int i = 1; i <= n + q; i++) {
    if(a[i].id <= n) {
      a[i].x = cmp[a[i].x]; 
    } else {
      a[i].x = cmp[*lower_bound(v.begin(), v.end(), a[i].x)];  
    }
  } 
  solve(1, n + q);
  for(int i = 1; i <= q; i++) printf("%d\n", ans[i + n]);
  return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &q);
   ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a[i].x, &a[i].y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57