제출 #499959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499959		cs142857	Examination (JOI19_examination)	C++17	100 / 100	2167 ms	67396 KiB

examination

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

#ifdef DBG
  #define dbg 1
  #define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
  #define Dps(...) Dbgs(__VA_ARGS__)
#else
  #define dbg 0
  #define dpf(...) 42
  #define Dps(...) 42
#endif
 
#define SIZE(c) int((c).size())
#define FOR(i,l,r) for(int i = (l); i < (r); ++i)
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;

template <typename T> inline bool UpdateMax(T& x, T v) {
  if(v > x) {x=v; return 1;} else return 0;
}
template <typename T> inline bool UpdateMin(T& x, T v) {
  if(v < x) {x=v; return 1;} else return 0;
}

template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;

inline namespace output {
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
  return os << "{" << v.first << " " << v.second << "}";
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "{";
  bool first = 1;
  REP(x, v) {
    if(first) first=0; else os << " ";
    os << x;
  }
  return os << "}";
}
}  // namespace output

inline namespace output {  // Only for debug now.
template <class T>
void PrSep(std::ostream& os, string, const T& t) { os << t; }
template <class T, class... U>
void PrSep(std::ostream& os, string sep, const T& t, const U&... u) {
  PrSep(os, sep, t); os << sep; PrSep(os, sep, u...);
}

// Print w/ spaces, end with newline
void Ps() { cout << "\n"; }
template<class ...T> void Ps(const T&... t) { PrSep(cout," ",t...); Ps(); } 
template<class ...T> void Dbgs(const T&... t) { PrSep(cerr," ",t...); cerr << endl; } 
}  // namespace output

template <typename K>
struct TrNode {
  K k;
  int pr = rand();
  int l = 0, r = 0;
  TrNode() {}
  TrNode(K k) : k(k) {}

  friend std::ostream& operator<<(std::ostream& os, const TrNode<K>& t) {
    return os << " {" << t.k << " " << t.pr << "}"
              << " {" << t.l << " " << t.r << "}";
  }
};

// Treap, Split/Merge, without rotation.
// Source: https://cp-algorithms.com/data_structures/treap.html
// Do not allow duplicate key.
template <typename K = int, typename V = TrNode<K>>
class Treap {
 public:
  vector<V> a;

  inline virtual void PushDown(int u) {}
  inline virtual void PushUp(int u) {}

  void Init(int init_capacity = 0) {
    a.resize(1);
    a.reserve(init_capacity + 1);
    empty_idx.clear();
  }

  void Split(int t, K k, int &l, int &r) {
    if (!t) {
      l = r = 0;
      return;
    }
    PushDown(t);
    if (k < a[t].k) {
      Split(a[t].l, k, l, a[t].l);
      r = t;
    } else {
      Split(a[t].r, k, a[t].r, r);
      l = t;
    }
    if (l) PushUp(l);
    if (r) PushUp(r);
  }

  // Merges two trees, all values of tree u must less than v.
  // Returns new root.
  int Merge(int l, int r) {
    if (l) PushDown(l);
    if (r) PushDown(r);
    if (!l) return r;
    if (!r) return l;
    int u;
    if (a[l].pr > a[r].pr) {
      a[l].r = Merge(a[l].r, r);
      u = l;
    } else {
      a[r].l = Merge(l, a[r].l);
      u = r;
    }
    PushUp(u);
    return u;
  }

  int NewNodeIdx() {
    int u;
    if (!empty_idx.empty()) {
      u = empty_idx.back();
      empty_idx.pop_back();
    } else {
      u = SIZE(a);
      a.emplace_back();
    }
    return u;
  }

  int NewNode(V v) {
    int i = NewNodeIdx();
    a[i] = v;
    return i;
  }

  void DelTree(int t) {
    if (!t) return;
    DelTree(a[t].l);
    DelTree(a[t].r);
    a[t].pr = 0;
    empty_idx.pb(t);
  }

  friend std::ostream& operator<<(std::ostream& os, const Treap<K, V>& t) {
    for (int i = 1; i < SIZE(t.a); ++i) {
      os << i << ": " << t.a[i] << "\n";
    }
    return os;
  }

 private:
  VI empty_idx;
};

template <typename K = int>
struct Node : TrNode<K> {
  K cnt = 0;  // Count of current node.
  K cnt_sub = 0;  // Count of sub-tree.

  Node() {}
  Node(K k) : TrNode<K>(k) {
    cnt = cnt_sub = 1;
  }

  friend std::ostream& operator<<(std::ostream& os, const Node& t) {
    return os << " {" << t.k << " " << t.pr << "}"
              << " {" << t.l << " " << t.r << "}"
              << " {" << t.cnt << " " << t.cnt_sub << "}";
  }
};

// Treap class with key count and size of sub-tree.
template <typename K = int>
class TreapWithCnt : public Treap<K, Node<K>> {
 public:
  using Base = Treap<K, Node<K>>;

  inline virtual void PushUp(int u) {
    this->a[u].cnt_sub = this->a[this->a[u].l].cnt_sub +
                         this->a[this->a[u].r].cnt_sub +
                         this->a[u].cnt;
  }

  void Insert(int& t, K k) {
    int l, r, m;
    this->Split(t, k, l, r);
    this->Split(l, k - 1, l, m);
    if (m) {
      this->a[m].cnt++;
      this->a[m].cnt_sub++;
    } else {
      m = this->NewNode(Node(k));
    }
    t = this->Merge(l, this->Merge(m, r));
  }

  // Returns false if k doesn't exist.
  void Delete(int& t, K k) {
    int l, r, m;
    this->Split(t, k, l, r);
    this->Split(l, k - 1, l, m);
    if (m) {
      this->a[m].cnt--;
      this->a[m].cnt_sub--;
      if (this->a[m].cnt == 0) {
        this->DelTree(m);
        m = 0;
      }
    }
    t = this->Merge(l, this->Merge(m, r));
  }

  // Gets the number of keys < k.
  int Rank(int root, K k) {
    int u = root;
    int res = 0;
    while (u) {
      if (this->a[u].k < k) {
        res += this->a[u].cnt_sub - this->a[this->a[u].r].cnt_sub;
        u = this->a[u].r;
      } else {
        u = this->a[u].l;
      }
    }
    return res;
  }
};

class SegTree2D {
 public:
  int max_idx;
  vector<int> a;
  TreapWithCnt<int> tree;

  SegTree2D() {
    tree.Init();
  }

  void Init(int max_idx) {
    int m = max_idx;
    this->max_idx = m;
    if(m < 0) {
      a.clear();
    } else {
      int c = 1;
      while (m) {
        ++c;
        m >>= 1;
      }
      a.resize(1 << c, 0);
    }
  }

  void Add(int x, int y) { Add(x, y, 1, 0, max_idx); }
  void Del(int x, int y) { Del(x, y, 1, 0, max_idx); }
  int Query(int qlx, int qrx, int y) { return Query(qlx, qrx, y, 1, 0, max_idx); }

 private:
  void Add(int x, int y, int p, int lx, int rx) {
   if (lx < rx) {
      int m = (lx + rx) >> 1, p1 = p << 1;
      if (x <= m) Add(x, y, p1, lx, m);
      else Add(x, y, p1 | 1, m + 1, rx);
    }
    tree.Insert(a[p], y);
  }

  void Del(int x, int y, int p, int lx, int rx) {
   if (lx < rx) {
      int m = (lx + rx) >> 1, p1 = p << 1;
      if (x <= m) Del(x, y, p1, lx, m);
      else Del(x, y, p1 | 1, m + 1, rx);
    }
    tree.Delete(a[p], y);
  }

  int Query(int qlx, int qrx, int y, int p, int lx, int rx) {
    if (qlx > rx || qrx < lx) return 0;
    if (qlx <= lx && qrx >= rx) {
      return tree.Rank(a[p], y);
    }
    int m = (lx + rx) >> 1, p1 = p << 1;
    return Query(qlx, qrx, y, p1, lx, m) + Query(qlx, qrx, y, p1 | 1, m + 1, rx);
  }
};

struct Score {
  int x, y, z;
};
vector<Score> a;

struct Query {
  int x, y, z;
  int idx;
};
vector<Query> qs;

void Solve() {
  int n,nq;
  scanf("%d%d",&n,&nq);
  a.resize(n);
  REP(x, a) {
    scanf("%d%d",&x.x,&x.y);
    x.z = x.x + x.y;
  }
  qs.resize(nq);
  FOR(i, 0, nq) {
    Query &q = qs[i];
    scanf("%d%d%d",&q.x, &q.y, &q.z);
    q.idx = i;
  }

  VI vx, vy;
  REP(x, a) {
    vx.pb(x.x);
    vy.pb(x.y);
  }
  sort(ALL(vx));
  vx.erase(unique(ALL(vx)), vx.end());
  sort(ALL(vy));
  vy.erase(unique(ALL(vy)), vy.end());

  sort(ALL(a), [](const Score& l, const Score& r) {
    return l.z < r.z;
  });
  REP(x, a) {
    x.x = lower_bound(ALL(vx), x.x) - vx.begin();
    x.y = lower_bound(ALL(vy), x.y) - vy.begin();
  }

  sort(ALL(qs), [](const Query &l, const Query &r) {
    return l.z < r.z;
  });

  VI ans(nq);
  SegTree2D st;
  st.Init(SIZE(vx) - 1);
  REP(x, a) st.Add(x.x, -x.y);

  int head = 0;
  REP(q, qs) {
    while(head < n && a[head].z < q.z) {
      st.Del(a[head].x, -a[head].y);
      ++head;
    }
    int x = lower_bound(ALL(vx), q.x) - vx.begin();
    int y = lower_bound(ALL(vy), q.y) - vy.begin();
    Dps("Query", q.idx, x, y);
    ans[q.idx] = st.Query(x, SIZE(vx) - 1, -y + 1);
    Dps(ans[q.idx]);
  }

  REP(x, ans) printf("%d\n",x);
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  for (int i = 1; i <= t; ++i) {
    // printf("Case #%d: ", i);
    Solve();
  }

  return 0;
}

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

examination.cpp: In function 'void Solve()':
examination.cpp:35:20: warning: statement has no effect [-Wunused-value]
   35 |   #define Dps(...) 42
      |                    ^~
examination.cpp:393:5: note: in expansion of macro 'Dps'
  393 |     Dps("Query", q.idx, x, y);
      |     ^~~
examination.cpp:35:20: warning: statement has no effect [-Wunused-value]
   35 |   #define Dps(...) 42
      |                    ^~
examination.cpp:395:5: note: in expansion of macro 'Dps'
  395 |     Dps(ans[q.idx]);
      |     ^~~
examination.cpp:345:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  345 |   scanf("%d%d",&n,&nq);
      |   ~~~~~^~~~~~~~~~~~~~~
examination.cpp:348:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  348 |     scanf("%d%d",&x.x,&x.y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:354:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  354 |     scanf("%d%d%d",&q.x, &q.y, &q.z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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