제출 #795322

#제출 시각아이디문제언어결과실행 시간메모리
795322acatmeowmeowExamination (JOI19_examination)C++11
100 / 100
986 ms55084 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5; int n, q, A[N + 5], B[N + 5], X[N + 5], Y[N + 5], Z[N + 5], arrIndex[N + 5], queryIndex[N + 5], ans[N + 5]; vector<int> node[2*N + 5], tree[2*N + 5]; void fakeUpdate(int x, int y) { for (; x <= 2*N; x += x&-x) node[x].push_back(y); } void fakeQuery(int x, int y){ for (; x; x -= x&-x) node[x].push_back(y); } void compress() { for (int i = 1; i <= 2*N; i++) { sort(node[i].begin(), node[i].end()); node[i].erase(unique(node[i].begin(), node[i].end()), node[i].end()); tree[i].resize(node[i].size() + 1); } } void update(int x, int y, int v) { for (; x <= 2*N; x += x&-x) { for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy <= node[x].size(); yy += yy&-yy) { tree[x][yy] += v; } } } int query(int x, int y) { int res = 0; for (; x; x -= x&-x) { for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy; yy -= yy&-yy) { res += tree[x][yy]; } } return res; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> A[i] >> B[i]; for (int i = 1; i <= q; i++) cin >> X[i] >> Y[i] >> Z[i]; vector<int> mp1, mp2; for (int i = 1; i <= n; i++) mp1.push_back(A[i]), mp2.push_back(B[i]); for (int i = 1; i <= q; i++) mp1.push_back(X[i]), mp2.push_back(Y[i]); sort(mp1.begin(), mp1.end()); sort(mp2.begin(), mp2.end()); auto getIndex = [&](int a, vector<int>&p) { return lower_bound(p.begin(), p.end(), a) - p.begin() + 1; }; iota(arrIndex + 1, arrIndex + n + 1, 1ll); sort(arrIndex + 1, arrIndex + n + 1, [&](int a, int b) { tuple<int, int, int> f = {A[a] + B[a], A[a], B[a]}, se = {A[b] + B[b], A[b], B[b]}; return f > se; }); iota(queryIndex + 1, queryIndex + q + 1, 1ll); sort(queryIndex + 1, queryIndex + q + 1, [&](int a, int b) { tuple<int, int, int> f = {Z[a], X[a], Y[a]}, se = {Z[b], X[b], Y[b]}; return f > se; }); for (int i = 1; i <= q; i++) { int mpX = getIndex(X[i], mp1), mpY = getIndex(Y[i], mp2); fakeQuery(2*N, 2*N); fakeQuery(2*N, mpY - 1); fakeQuery(mpX - 1, 2*N); fakeQuery(mpX - 1, mpY - 1); } for (int i = 1; i <= n; i++) { int mpA = getIndex(A[i], mp1), mpB = getIndex(B[i], mp2); fakeUpdate(mpA, mpB); } compress(); for (int i = 1, index = 1; i <= q; i++) { int pos = queryIndex[i]; while (index <= n && A[arrIndex[index]] + B[arrIndex[index]] >= Z[pos]) { int mpA = getIndex(A[arrIndex[index]], mp1), mpB = getIndex(B[arrIndex[index]], mp2); update(mpA, mpB, 1); index++; } int mpX = getIndex(X[pos], mp1), mpY = getIndex(Y[pos], mp2); ans[pos] = query(2*N, 2*N) - query(2*N, mpY - 1) - query(mpX - 1, 2*N) + query(mpX - 1, mpY - 1); } for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'void update(int, int, int)':
examination.cpp:27:90: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy <= node[x].size(); yy += yy&-yy) {
      |                                                                                       ~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...