Submission #613637

#TimeUsernameProblemLanguageResultExecution timeMemory
613637talant117408Examination (JOI19_examination)C++17
100 / 100
266 ms18912 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> // Общий файл. #include <ext/pb_ds/tree_policy.hpp> // Содержит класс tree_order_statistics_node_update using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' #define PI 2*acos(0.0) void solve(int test) { int n, q; cin >> n >> q; vector <int> a(n), b(n); vector <pair <pii, pii>> queries(q); for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; } for (int i = 0; i < q; i++) { auto &to = queries[i]; cin >> to.first.first >> to.first.second >> to.second.first; to.second.second = i; } vector <int> inds(n); iota(all(inds), 0); sort(all(inds), [&](int i, int j) { return a[i] < a[j]; }); int i = n - 1; ordered_set st; sort(rall(queries)); vector <int> ans(q); for (auto to : queries) { auto x = to.first.first, y = to.first.second, z = to.second.first; if (x + y < z) continue; auto ind = to.second.second; while (i >= 0 && a[inds[i]] >= x) { st.insert(b[inds[i--]]); } ans[ind] = sz(st) - st.order_of_key(y); } sort(all(inds), [&](int i, int j) { return a[i] + b[i] < a[j] + b[j]; }); i = n - 1; ordered_set math, infor; sort(all(queries), [&](pair <pii, pii> i, pair <pii, pii> j) { return i.second.first > j.second.first; }); for (auto to : queries) { auto x = to.first.first, y = to.first.second, z = to.second.first; if (x + y >= z) continue; auto ind = to.second.second; while (i >= 0 && a[inds[i]] + b[inds[i]] >= z) { math.insert(a[inds[i]]); infor.insert(b[inds[i]]); i--; } int saizu = n - i - 1; ans[ind] = (saizu - math.order_of_key(x)) + (saizu - infor.order_of_key(y)) - saizu; } for (auto to : ans) cout << to << endl; } int main() { do_not_disturb int t = 1; //~ cin >> t; for (int i = 1; i <= t; i++) { solve(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...