oj.uz

Submission #499959

# Submission time Handle Problem Language Result Execution time Memory
499959 2021-12-30T06:22:27 Z cs142857 Examination (JOI19_examination) C++17
100 / 100
 2167 ms 67396 KB 
#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;
}

Compilation message

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 23 ms 2220 KB Output is correct
8 Correct 23 ms 2192 KB Output is correct
9 Correct 24 ms 2244 KB Output is correct
10 Correct 14 ms 1048 KB Output is correct
11 Correct 9 ms 988 KB Output is correct
12 Correct 5 ms 436 KB Output is correct
13 Correct 21 ms 2200 KB Output is correct
14 Correct 16 ms 2244 KB Output is correct
15 Correct 20 ms 2252 KB Output is correct
16 Correct 4 ms 652 KB Output is correct
17 Correct 7 ms 844 KB Output is correct
18 Correct 2 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1583 ms 57040 KB Output is correct
2 Correct 1550 ms 56944 KB Output is correct
3 Correct 1494 ms 56804 KB Output is correct
4 Correct 412 ms 19136 KB Output is correct
5 Correct 322 ms 18852 KB Output is correct
6 Correct 112 ms 5952 KB Output is correct
7 Correct 1470 ms 56760 KB Output is correct
8 Correct 1197 ms 56928 KB Output is correct
9 Correct 1140 ms 56632 KB Output is correct
10 Correct 120 ms 8200 KB Output is correct
11 Correct 146 ms 10156 KB Output is correct
12 Correct 48 ms 5528 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1583 ms 57040 KB Output is correct
2 Correct 1550 ms 56944 KB Output is correct
3 Correct 1494 ms 56804 KB Output is correct
4 Correct 412 ms 19136 KB Output is correct
5 Correct 322 ms 18852 KB Output is correct
6 Correct 112 ms 5952 KB Output is correct
7 Correct 1470 ms 56760 KB Output is correct
8 Correct 1197 ms 56928 KB Output is correct
9 Correct 1140 ms 56632 KB Output is correct
10 Correct 120 ms 8200 KB Output is correct
11 Correct 146 ms 10156 KB Output is correct
12 Correct 48 ms 5528 KB Output is correct
13 Correct 2167 ms 60648 KB Output is correct
14 Correct 1968 ms 57224 KB Output is correct
15 Correct 1491 ms 56784 KB Output is correct
16 Correct 568 ms 20560 KB Output is correct
17 Correct 434 ms 19236 KB Output is correct
18 Correct 120 ms 5944 KB Output is correct
19 Correct 2110 ms 60604 KB Output is correct
20 Correct 2157 ms 59880 KB Output is correct
21 Correct 1920 ms 60732 KB Output is correct
22 Correct 110 ms 8112 KB Output is correct
23 Correct 128 ms 10132 KB Output is correct
24 Correct 49 ms 5660 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 23 ms 2220 KB Output is correct
8 Correct 23 ms 2192 KB Output is correct
9 Correct 24 ms 2244 KB Output is correct
10 Correct 14 ms 1048 KB Output is correct
11 Correct 9 ms 988 KB Output is correct
12 Correct 5 ms 436 KB Output is correct
13 Correct 21 ms 2200 KB Output is correct
14 Correct 16 ms 2244 KB Output is correct
15 Correct 20 ms 2252 KB Output is correct
16 Correct 4 ms 652 KB Output is correct
17 Correct 7 ms 844 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 1583 ms 57040 KB Output is correct
20 Correct 1550 ms 56944 KB Output is correct
21 Correct 1494 ms 56804 KB Output is correct
22 Correct 412 ms 19136 KB Output is correct
23 Correct 322 ms 18852 KB Output is correct
24 Correct 112 ms 5952 KB Output is correct
25 Correct 1470 ms 56760 KB Output is correct
26 Correct 1197 ms 56928 KB Output is correct
27 Correct 1140 ms 56632 KB Output is correct
28 Correct 120 ms 8200 KB Output is correct
29 Correct 146 ms 10156 KB Output is correct
30 Correct 48 ms 5528 KB Output is correct
31 Correct 2167 ms 60648 KB Output is correct
32 Correct 1968 ms 57224 KB Output is correct
33 Correct 1491 ms 56784 KB Output is correct
34 Correct 568 ms 20560 KB Output is correct
35 Correct 434 ms 19236 KB Output is correct
36 Correct 120 ms 5944 KB Output is correct
37 Correct 2110 ms 60604 KB Output is correct
38 Correct 2157 ms 59880 KB Output is correct
39 Correct 1920 ms 60732 KB Output is correct
40 Correct 110 ms 8112 KB Output is correct
41 Correct 128 ms 10132 KB Output is correct
42 Correct 49 ms 5660 KB Output is correct
43 Correct 2117 ms 67396 KB Output is correct
44 Correct 2045 ms 67232 KB Output is correct
45 Correct 1986 ms 59688 KB Output is correct
46 Correct 581 ms 24300 KB Output is correct
47 Correct 387 ms 22544 KB Output is correct
48 Correct 139 ms 5816 KB Output is correct
49 Correct 1795 ms 59600 KB Output is correct
50 Correct 1868 ms 67248 KB Output is correct
51 Correct 1574 ms 59560 KB Output is correct
52 Correct 182 ms 11144 KB Output is correct
53 Correct 137 ms 14220 KB Output is correct