Submission #965717

#TimeUsernameProblemLanguageResultExecution timeMemory
965717becaidoExamination (JOI19_examination)C++17
100 / 100
191 ms14136 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> using namespace std; #ifdef WAIMAI #define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE) void dout() {cout << '\n';} template<typename T, typename...U> void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);} #else #define debug(...) 7122 #endif #define ll long long #define Waimai ios::sync_with_stdio(false), cin.tie(0) #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back #define F first #define S second const int SIZE = 2e5 + 5; int n, q, sz; int ans[SIZE]; int m; vector<int> lis; int bit[SIZE]; void upd(int pos, int x) { for (; pos <= m; pos += pos & -pos) bit[pos] += x; } int que(int pos) { int re = 0; for (; pos; pos -= pos & -pos) re += bit[pos]; return re; } struct ds { int x, y, z, id; ds() {} ds(int x, int y, int z, int id) : x(x), y(y), z(z), id(id) {} bool operator < (const ds &o) const { return make_tuple(x, y, z, id) < make_tuple(o.x, o.y, o.z, o.id); } } a[SIZE], tmp[SIZE]; bool cmp(ds a, ds b) { // return a < b return make_tuple(a.y, a.z, a.id) < make_tuple(b.y, b.z, b.id); } void divide(int l, int r) { if (l == r) return; int mid = (l + r) / 2; divide(l, mid), divide(mid + 1, r); debug(l, r); for (int i = l, il = l, ir = mid + 1; i <= r; i++) { if (ir > r || (il <= mid && cmp(a[il], a[ir]))) { if (a[il].id == 0) upd(a[il].z, 1); tmp[i] = a[il++]; } else { if (a[ir].id) ans[a[ir].id] += que(a[ir].z); tmp[i] = a[ir++]; } } FOR (i, l, mid) if (a[i].id == 0) upd(a[i].z, -1); FOR (i, l, r) a[i] = tmp[i]; } void solve() { cin >> n >> q; FOR (i, 1, n) { int x, y; cin >> x >> y; x = -x, y = -y; a[++sz] = ds(x, y, x + y, 0); } FOR (i, 1, q) { int x, y, z; cin >> x >> y >> z; x = -x, y = -y, z = -z; a[++sz] = ds(x, y, z, i); } FOR (i, 1, sz) lis.pb(a[i].z); sort(lis.begin(), lis.end()); lis.erase(unique(lis.begin(), lis.end()), lis.end()); m = lis.size(); FOR (i, 1, sz) a[i].z = lower_bound(lis.begin(), lis.end(), a[i].z) - lis.begin() + 1; sort(a + 1, a + sz + 1); divide(1, sz); FOR (i, 1, q) cout << ans[i] << '\n'; } int main() { Waimai; solve(); } /* in1 5 4 35 100 70 70 45 15 80 40 20 95 20 50 120 10 10 100 60 60 80 0 100 100 out1 2 4 1 1 in2 10 10 41304 98327 91921 28251 85635 59191 30361 72671 28949 96958 99041 37826 10245 2726 19387 20282 60366 87723 95388 49726 52302 69501 66009 43754 45346 3158 25224 58881 18727 7298 24412 63782 24107 10583 61508 65025 29140 7278 36104 56758 2775 23126 67608 122051 56910 17272 62933 39675 15874 117117 out2 1 3 5 8 8 3 3 3 5 6 */

Compilation message (stderr)

examination.cpp: In function 'void divide(int, int)':
examination.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 7122
      |                    ^~~~
examination.cpp:57:5: note: in expansion of macro 'debug'
   57 |     debug(l, r);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...