Submission #331325

#TimeUsernameProblemLanguageResultExecution timeMemory
331325FalconMatryoshka (JOI16_matryoshka)C++17
100 / 100
347 ms17112 KiB
#pragma GCC optimize("O2") #include <bits/stdc++.h> #ifdef DEBUG #include "debug.hpp" #endif using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it) #define rep(i, N) for(int i = 0; i < (N); ++i) #define rrep(i, N) for(int i = (N) - 1; i >= 0; --i) #define rep1(i, N) for(int i = 1; i <= (N); ++i) #define rep2(i, s, e) for(int i = (s); i <= (e); ++i) #define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d)) #ifdef DEBUG #define debug(x...) { \ ++dbg::depth; \ string dbg_vals = dbg::to_string(x); \ --dbg::depth; \ dbg::fprint(__func__, __LINE__, #x, dbg_vals); \ } #define light_debug(x) { \ dbg::light = true; \ dbg::dout << __func__ << ":" << __LINE__; \ dbg::dout << " " << #x << " = " << x << endl; \ dbg::light = false; \ } #else #define debug(x...) 42 #define light_debug(x) 42 #endif using ll = long long; template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; } template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; } template<int n> class segment_tree { array<int, n << 1> a; public: void update(int i, int v) { for(a[i += n] = v, i >>= 1; i > 0; i >>= 1) a[i] = max(a[i << 1], a[i << 1 | 1]); } int query(int s, int e) const { int r{}; for(s += n, e += n; s < e; s >>= 1, e >>= 1) { if(s & 1) ckmax(r, a[s++]); if(e & 1) ckmax(r, a[--e]); } return r; } }; constexpr int MAXV{2'00'000}; segment_tree<MAXV> seg; int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef DEBUG freopen("debug", "w", stderr); #endif int N, Q; cin >> N >> Q; vector<pair<int, int>> v(N); rep(i, N) cin >> v[i].first >> v[i].second, v[i].second = MAXV - v[i].second; sort(rall(v)); struct compress { vector<int> values; void insert(int x) { values.push_back(x); } void apply() { sort(all(values)); values.erase(unique(all(values)), values.end()); } int get_rank(int x) const { return int(lower_bound(all(values), x) - values.begin()); } }; compress X, Y; for(const auto& [x, y] : v) X.insert(x), Y.insert(y); X.apply(), Y.apply(); for(auto& [x, y] : v) x = X.get_rank(x), y = Y.get_rank(y); struct query { int A, B, i; }; vector<query> queries; queries.reserve(Q); rep(i, Q) { int A, B; cin >> A >> B; B = MAXV - B; A = X.get_rank(A), B = Y.get_rank(B); queries.push_back({A, B, i}); } sort(rall(queries),[](const query& a, const query& b) { return a.A < b.A; }); auto p = v.begin(); vector<int> ans(Q); for(const query& q : queries) { debug(q.i, q.A, q.B); for(; p != v.end() && p->first >= q.A; ++p) { debug(*p, 1 + seg.query(p->second, MAXV)); seg.update(p->second, 1 + seg.query(p->second, MAXV)); } ans[q.i] = seg.query(q.B, MAXV); } for(int x : ans) cout << x << '\n'; #ifdef DEBUG dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC << "ms" << endl; #endif return 0; }

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
matryoshka.cpp:121:9: note: in expansion of macro 'debug'
  121 |         debug(q.i, q.A, q.B);
      |         ^~~~~
matryoshka.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
matryoshka.cpp:123:13: note: in expansion of macro 'debug'
  123 |             debug(*p, 1 + seg.query(p->second, MAXV));
      |             ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...