제출 #261198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261198		Bruteforceman	Examination (JOI19_examination)	C++11	2 / 100	3035 ms	195720 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int maxn = 2e5 + 10;
typedef pair <int, int> pii;
typedef tree <pii,
              null_type,
              less <pii>,
              rb_tree_tag,
              tree_order_statistics_node_update> orderset;
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];

orderset t[maxn * 4];
int ans[maxn];
int idx;
void add(int x, int y, int id, int c = 1, int b = 1, int e = idx) {
  t[c].insert(pii(y, id));
  if(b == e) return ;
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  if(x <= m) add(x, y, id, l, b, m);
  else add(x, y, id, r, m + 1, e);
}
int query(int x, int y, int val, int c = 1, int b = 1, int e = idx) {
  if(x <= b && e <= y) {
    return t[c].size() - t[c].order_of_key(pii(val, -1));
  }
  if(y < b || e < x) return 0;
  int m = (b + e) >> 1;
  int l = c << 1;
  int r = l + 1;
  return query(x, y, val, l, b, m) + query(x, y, val, r, m + 1, e);
}

int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  map <int, int> cmp;
  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];
  }
  for(int i = n + 1; i <= n + q; i++) {
    scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
    cmp[a[i].x];
    a[i].id = i;
  }
  sort(a + 1, a + n + q + 1);
  idx = 0;
  for(auto &i : cmp) {
    i.second = ++idx;
  }
  for(int i = 1; i <= n + q; i++) {
    a[i].x = cmp[a[i].x];
  }
  for(int i = 1; i <= n + q; i++) {
    if(a[i].id > n) {
      ans[a[i].id - n] = query(a[i].x, idx, a[i].y);
    } else {
      add(a[i].x, a[i].y, a[i].id);
    }
  }
  for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:51: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:54: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:60: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