Submission #716964

#TimeUsernameProblemLanguageResultExecution timeMemory
716964walterwExamination (JOI19_examination)C++17
0 / 100
3066 ms9728 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; vector<array<int, 5>> queries; vector<int> comp; int ans[500005]; struct tree { int arr[500005]; void add(int x) { for(; x < 500005; x += x & (-x)) { arr[x]++; } } int query(int lowerbound) { int tot = 0; for (int x = 500004; x > 0; x -= x & (-x)) { tot += arr[x]; } int subtract = 0; for (int x = lowerbound - 1; x > 0; x -= x & (-x)) { subtract += arr[x]; } return tot - subtract; } } x, y; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { int s, t; cin >> s >> t; comp.push_back(s); comp.push_back(t); queries.push_back({s + t, s, t, 1, -1}); } for (int i = 1; i <= q; i++) { int a, b, c; cin >> a >> b >> c; comp.push_back(a); comp.push_back(b); queries.push_back({max(c, a + b), a, b, -1, i}); } sort(queries.begin(), queries.end(), [](array<int, 5> a, array<int, 5> b) { if (a[0] == b[0]) { return a[3] > b[3]; } return a[0] > b[0]; }); sort(comp.begin(), comp.end()); auto idx = [&](int a) { return lower_bound(comp.begin(), comp.end(), a) - comp.begin() + 1; }; int total = 0; for (auto [a, b, c, d, e] : queries) { if (d == 1) { // add x.add(b); y.add(c); total++; } else { ans[e] = x.query(b) + y.query(c) - total; } } for (int i = 1; i <= q; i++) cout << ans[i] << "\n"; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:91:10: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
   91 |     auto idx = [&](int a) {
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...