Submission #1102802

#TimeUsernameProblemLanguageResultExecution timeMemory
1102802IcelastExamination (JOI19_examination)C++17
2 / 100
1130 ms1048576 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; struct point{ ll x, y, z, id; }; struct normalize{ vector<ll> poi, pot; void add(ll x){ poi.push_back(x); } void start(){ sort(poi.begin(), poi.end()); pot.push_back(poi[0]); for(int i = 1; i < (int)poi.size(); i++){ if(poi[i] != poi[i-1]){ pot.push_back(poi[i]); } } } int encode(ll x){ return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1; } }; struct Fenwick2D { int n, m; vector<vector<int>> bit; vector<vector<int>> f; Fenwick2D(int n, int m) : n(n), m(m), bit(n + 1), f(n + 1) {} void fakeAdd(int i0, int j0) { for (int i = i0; i <= n; i += i & -i) { for (int j = j0; j <= m; j += j & -j) { f[i].push_back(j); } } } void work() { for (int i = 1; i <= n; i++) { f[i].push_back(0); sort(f[i].begin(), f[i].end()); f[i].resize(unique(f[i].begin(), f[i].end()) - f[i].begin()); bit[i].resize(f[i].size(), 0); } } void add(int i0, int j0, int x) { for (int i = i0; i <= n; i += i & -i) { for (int j = lower_bound(f[i].begin(), f[i].end(), j0) - f[i].begin(); j < (int)f[i].size(); j += j & -j) { bit[i][j] += x; } } } int sum(int i0, int j0) { int res = 0; for (int i = i0; i > 0; i -= i & -i) { for (int j = upper_bound(f[i].begin(), f[i].end(), j0) - f[i].begin() - 1; j > 0; j -= j & -j) { res += bit[i][j]; } } return res; } }; void solve(){ int n, Q; cin >> n >> Q; vector<point> a(n+1); for(int i = 1; i <= n; i++){ cin >> a[i].x >> a[i].y; a[i].z = a[i].x+a[i].y; } vector<point> q(Q+1); for(int i = 1; i <= Q; i++){ cin >> q[i].x >> q[i].y >> q[i].z; q[i].id = i; } normalize norm; for(int i = 1; i <= n; i++){ norm.add(a[i].x); norm.add(a[i].y); norm.add(a[i].z); } for(int i = 1; i <= Q; i++){ norm.add(q[i].x); norm.add(q[i].y); norm.add(q[i].z); } norm.start(); int N = norm.pot.size(); for(int i = 1; i <= n; i++){ a[i].x = N-norm.encode(a[i].x); a[i].y = N-norm.encode(a[i].y); a[i].z = norm.encode(a[i].z); } for(int i = 1; i <= Q; i++){ q[i].x = N-norm.encode(q[i].x); q[i].y = N-norm.encode(q[i].y); q[i].z = norm.encode(q[i].z); } Fenwick2D bit(N+1, N+1); for(int i = 1; i <= n; i++){ bit.fakeAdd(a[i].x, a[i].y); } bit.work(); sort(a.begin()+1, a.end(), [&](point a, point b){return a.z > b.z;}); sort(q.begin()+1, q.end(), [&](point a, point b){return a.z > b.z;}); vector<ll> ans(Q+1); int j = 1; for(int i = 1; i <= Q; i++){ while(j <= n && a[j].z >= q[i].z){ bit.add(a[j].x, a[j].y, 1); j++; } ans[q[i].id] = bit.sum(q[i].x, q[i].y); } for(int i = 1; i <= Q; i++){ cout << ans[i] << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...