제출 #201045

#제출 시각아이디문제언어결과실행 시간메모리
201045extraterrestrialExamination (JOI19_examination)C++14
2 / 100
3092 ms278464 KiB
#include <bits/stdc++.h> typedef long long ll; typedef long double ld; using namespace std; #define F first #define S second #define pb push_back #define all(x) (x).begin(), (x).end() #define SZ(x) (int)(x).size() //#define int ll struct query { int a, b, sum, id; query() {}; query(int a, int b, int sum, int id) : a(a), b(b), sum(sum), id(id) {}; }; const int N = 1e5 + 10; unordered_map<int, int> t[N]; int ans[N], sz1, sz2; inline void update(int a, int b) { for (int i = a; i <= sz1; i += i & (-i)) { for (int j = b; j <= sz2; j += j & (-j)) { t[i][j]++; } } } inline int get(int a, int b) { int res = 0; for (int i = a; i > 0; i -= i & (-i)) { for (int j = b; j > 0; j -= j & (-j)) { res += t[i][j]; } } return res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> a(n), b(n), sa, sb, ss; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; sa.pb(a[i]); sb.pb(b[i]); ss.pb(a[i] + b[i]); } vector<query> que(m); for (int i = 0; i < m; i++) { cin >> que[i].a >> que[i].b >> que[i].sum; que[i].id = i; sa.pb(que[i].a); sb.pb(que[i].b); ss.pb(que[i].sum); } sort(all(sa)); sort(all(sb)); sort(all(ss)); sa.resize(unique(all(sa)) - sa.begin()); sb.resize(unique(all(sb)) - sb.begin()); ss.resize(unique(all(ss)) - ss.begin()); vector<vector<pair<int, int>>> add(SZ(ss)); for (int i = 0; i < n; i++) { int cs = lower_bound(all(ss), a[i] + b[i]) - ss.begin(); a[i] = upper_bound(all(sa), a[i]) - sa.begin(); b[i] = upper_bound(all(sb), b[i]) - sb.begin(); //cerr << a[i] << ' ' << b[i] << ' ' << cs << '\n'; add[cs].pb({a[i], b[i]}); } vector<vector<pair<pair<int, int>, int>>> check(SZ(ss)); for (int i = 0; i < m; i++) { que[i].sum = lower_bound(all(ss), que[i].sum) - ss.begin(); que[i].a = upper_bound(all(sa), que[i].a) - sa.begin(); que[i].b = upper_bound(all(sb), que[i].b) - sb.begin(); //cout << que[i].a << ' ' << que[i].b << ' ' << que[i].sum << '\n'; check[que[i].sum].pb(make_pair(make_pair(que[i].a, que[i].b), que[i].id)); } sz1 = SZ(sa), sz2 = SZ(sb); for (int i = SZ(ss) - 1; i >= 0; i--) { for (auto it : add[i]) { update(SZ(sa) - it.F + 1, SZ(sb) - it.S + 1); } for (auto it : check[i]) { ans[it.S] = get(SZ(sa) - it.F.F + 1, SZ(sb) - it.F.S + 1); } } for (int i = 0; i < m; i++) { cout << ans[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...