Submission #330282

#TimeUsernameProblemLanguageResultExecution timeMemory
330282dolphingarlicMatryoshka (JOI16_matryoshka)C++14
100 / 100
653 ms140524 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; struct Node { int l, r, val; Node *lc, *rc; Node(int L, int R): l(L), r(R), val(0), lc(nullptr), rc(nullptr) {} void update(int p, int v) { val = max(val, v); if (l != r) { int mid = (l + r) / 2; if (p > mid) { if (!rc) rc = new Node(mid + 1, r); rc->update(p, v); } else { if (!lc) lc = new Node(l, mid); lc->update(p, v); } } } int query(int a, int b) { if (r < a || l > b) return 0; if (r <= b && l >= a) return val; int ret = 0; if (lc) ret = max(ret, lc->query(a, b)); if (rc) ret = max(ret, rc->query(a, b)); return ret; } }; pair<int, int> doll[200000]; pair<pair<int, int>, int> query[200000]; int lis[200000], ans[200000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { cin >> doll[i].first >> doll[i].second; doll[i].second = -doll[i].second; } for (int i = 0; i < q; i++) { cin >> query[i].first.first >> query[i].first.second; query[i].second = i; } sort(doll, doll + n, greater<pair<int, int>>()); sort(query, query + q, greater<pair<pair<int, int>, int>>()); vector<int> dp; for (int i = 0; i < n; i++) { lis[i] = upper_bound(dp.begin(), dp.end(), -doll[i].second) - dp.begin(); if (lis[i] == dp.size()) dp.push_back(-doll[i].second); else dp[lis[i]] = -doll[i].second; lis[i]++; } Node *segtree = new Node(1, 1000000000); for (int i = 0, j = 0; i < q; i++) { while (j < n && doll[j].first >= query[i].first.first) { segtree->update(-doll[j].second, lis[j]); j++; } ans[query[i].second] = segtree->query(1, query[i].first.second); } for (int i = 0; i < q; i++) cout << ans[i] << '\n'; return 0; }

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if (lis[i] == dp.size()) dp.push_back(-doll[i].second);
      |             ~~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...