Submission #522080

#TimeUsernameProblemLanguageResultExecution timeMemory
522080sidonMatryoshka (JOI16_matryoshka)C++17
100 / 100
242 ms20548 KiB
#include <bits/stdc++.h> using namespace std; int N, Q, INF = 2e9; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> N >> Q; array<int, 2> a[N], _; vector<array<int, 2>> qAt[N]; for(auto &[r, h] : a) cin >> r >> h, r = -r; sort(a, a+N); int res[Q] = {}; for(int i = 0; i < Q; ++i) { int A, B; cin >> A >> B; if(a[0][0] <= -A) qAt[lower_bound(a, a+N, _={-A, INF}) - a - 1].push_back({B, i}); } int L[N], *R = L; for(int i = 0; i < N; ++i) { int v = a[i][1]; if(!i || R[-1] <= v) *R++ = v; else *upper_bound(L, R, v) = v; for(auto &[w, qI] : qAt[i]) res[qI] = upper_bound(L, R, w) - L; } for(int &i : res) cout << i << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...