Submission #383918

#TimeUsernameProblemLanguageResultExecution timeMemory
383918nikatamlianiExamination (JOI19_examination)C++14
100 / 100
1121 ms70428 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; template <typename T> struct segment_tree { vector<T> tree; T neutral; int size; function<T(T, T)> join; segment_tree(int _size, T _neutral, function<T(T, T)> f) { join = f; size = _size; tree = vector<T>(4 * size); neutral = _neutral; } void point_update(int id, T val) { point_update(1, size, id, val, 1); } void point_update(int l, int r, int x, T val, int p) { if(l > x || r < x) { return; } if(l == r) { tree[p] = val; return; } int middle = l + r >> 1; point_update(l, middle, x, val, p << 1); point_update(middle+1, r, x, val, p << 1 | 1); tree[p] = join(tree[p << 1], tree[p << 1 | 1]); } T get(int id) { return query(id, id); } T query(int L, int R) { return query(1, size, L, R, 1); } T query(int l, int r, int L, int R, int p) { if(L > r || l > R) return neutral; if(L <= l && R >= r) return tree[p]; int middle = l + r >> 1; T lft = query(l, middle, L, R, p << 1); T rgh = query(middle+1, r, L, R, p << 1 | 1); return join(lft, rgh); } }; map<int, int> compress(vector<int> &coords) { sort(coords.begin(), coords.end()); map<int, int> compressed; for(int i = 0, current = 0; i < (int)coords.size(); ++i) { if(i == 0 || coords[i] != coords[i - 1]) ++current; compressed[coords[i]] = current; } return compressed; } int x[N], y[N], a[N], b[N], c[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<vector<int>> v; vector<int> sorted_sums; for(int i = 1; i <= n; ++i) { cin >> x[i] >> y[i]; sorted_sums.push_back(x[i] + y[i]); v.push_back({x[i], y[i]}); } sort(sorted_sums.begin(), sorted_sums.end()); sort(v.begin(), v.end()); for(int i = 1; i <= n; ++i) { x[i] = v[i - 1][0]; y[i] = v[i - 1][1]; } v.clear(); for(int i = 1; i <= m; ++i) { cin >> a[i] >> b[i] >> c[i]; } vector<int> type1, type2; for(int i = 1; i <= m; ++i) { if(a[i] + b[i] >= c[i]) { type1.push_back(i); } else { type2.push_back(i); } } map<int, int> compressed_sum, compressed_x, compressed_y; //sum vector<int> coords(n + m); for(int i = 1; i <= m; ++i) { coords[i - 1] = c[i]; } for(int i = 1; i <= n; ++i) { coords[i + m - 1] = x[i] + y[i]; } compressed_sum = compress(coords); //x for(int i = 1; i <= m; ++i) { coords[i - 1] = a[i]; } for(int i = 1; i <= n; ++i) { coords[i + m - 1] = x[i]; } compressed_x = compress(coords); //y for(int i = 1; i <= m; ++i) { coords[i - 1] = b[i]; } for(int i = 1; i <= n; ++i) { coords[i + m - 1] = y[i]; } compressed_y = compress(coords); sort(type1.begin(), type1.end(), [&](int x, int y) { if(a[x] == a[y]) { if(b[x] == b[y]) { return c[x] < c[y]; } return b[x] < b[y]; } return a[x] < a[y]; }); auto sum = [](int x, int y) -> int { return x + y; }; segment_tree<int> t(N, 0, sum); segment_tree<int> tx(N, 0, sum); segment_tree<int> ty(N, 0, sum); vector<int> ans(m+1); for(int i = (int)type1.size() - 1, j = n; i >= 0; --i) { int q_id = type1[i]; while(j > 0 && x[j] >= a[q_id]) { int val = compressed_y[y[j]]; t.point_update(val, t.get(val)+1); --j; } int val = compressed_y[b[q_id]]; ans[q_id] = t.query(val, t.size); } for(int i : type2) { int l = 0, r = n - 1, ind = n; while(r >= l) { int middle = l + r >> 1; if(sorted_sums[middle] >= c[i]) { r = middle - 1; ind = middle; } else { l = middle + 1; } } // all[i] = n - ind; ans[i] = n - ind; } vector<int> sums[N], queries[N]; for(int i = 1; i <= n; ++i) { int val = compressed_sum[x[i] + y[i]]; sums[val].push_back(i); } for(int i : type2) { if(i == -1) continue; int val = compressed_sum[c[i]]; queries[val].push_back(i); } int max_sum_val = (int)compressed_sum.size(); for(int i = max_sum_val; i >= 1; --i) { for(int id : sums[i]) { int val_x = compressed_x[x[id]]; int val_y = compressed_y[y[id]]; tx.point_update(val_x, tx.get(val_x)+1); ty.point_update(val_y, ty.get(val_y)+1); } for(int id : queries[i]) { int val_x = compressed_x[a[id]]; int val_y = compressed_y[b[id]]; /* sumA[id] */ ans[id] -= tx.query(1, val_x - 1); /* sumB[id] */ ans[id] -= ty.query(1, val_y - 1); } } for(int i = 1; i <= m; ++i) { cout << ans[i] << '\n'; } // for (int i = 1; i <= m; ++i) { // if (a[i] + b[i] >= c[i]) { // int ans = 0; // for(int j = 1; j <= n; ++j) { // if (x[j] >= a[i] && y[j] >= b[i]) { // ++ans; // } // } // cout << ans << '\n'; // continue; // } // int all = 0, sumA = 0, sumB = 0; // for (int j = 1; j <= n; ++j) { // if (x[j] + y[j] >= c[i]) { // ++all; // } // if (x[j] < a[i] && x[j] + y[j] >= c[i]) { // ++sumA; // } // if (y[j] < b[i] && x[j] + y[j] >= c[i]) { // ++sumB; // } // } // cout << all - sumA - sumB << '\n'; // } }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:146:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |    int middle = l + r >> 1;
      |                 ~~^~~
examination.cpp: In instantiation of 'void segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
examination.cpp:18:3:   required from 'void segment_tree<T>::point_update(int, T) [with T = int]'
examination.cpp:137:36:   required from here
examination.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int middle = l + r >> 1;
      |                ~~^~~
examination.cpp: In instantiation of 'T segment_tree<T>::query(int, int, int, int, int) [with T = int]':
examination.cpp:40:32:   required from 'T segment_tree<T>::query(int, int) [with T = int]'
examination.cpp:141:34:   required from here
examination.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int middle = l + r >> 1;
      |                ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...