Submission #1212384

#TimeUsernameProblemLanguageResultExecution timeMemory
1212384akamizanePairs (IOI07_pairs)C++20
100 / 100
181 ms60048 KiB
#include<bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #else #define debug(...) 42 #endif #define int long long template<class T, int... Ns> struct BIT { T val = 0; void upd(T v) { val += v; } T query() { return val; } }; template<class T, int N, int... Ns> struct BIT<T, N, Ns...> { BIT<T, Ns...> bit[N+1]; template<typename... Args> void upd(int pos, Args... args) { for (; pos <= N; pos += pos&-pos) bit[pos].upd(args...); } template<typename... Args> T sum(int pos, Args... args) { T res = 0; for (; pos > 0; pos -= pos&-pos) res += bit[pos].query(args...); return res; } template<typename... Args> T query(int l, int r, Args... args) { return sum(r, args...) - sum(l-1, args...); } }; int b, n, d, m, ans = 0; BIT<int, 301, 301, 301> bit; namespace sub1 { void solve() { vector<int> a(n); for (auto& x : a) cin >> x; sort(a.begin(), a.end()); debug(a); int l = 0, r = 0; for (int i = 0; i < n; i++){ while(r + 1 < n && a[r + 1] - a[i] <= d) r++; while(l < n && a[i] - a[l] > d) l++; ans += r - l; } } } namespace sub2 { void solve(){ vector<array<int, 2>> a(n); for (int i = 0; i < n; i++){ int x, y; cin >> x >> y; a[i] = {x + y, x - y}; } sort(a.begin(), a.end()); int l = 0, r = -1; BIT<int, 150001> bit; for (int i = 0; i < n; i++){ while(r + 1 < n && a[r + 1][0] - a[i][0] <= d){ bit.upd(a[++r][1] + m + 1, 1); } while(l < n && a[i][0] - a[l][0] > d){ bit.upd(a[l++][1] + m + 1, -1); } ans += bit.query(max(1ll, a[i][1] + m + 1 - d), min(2 * m + 1, a[i][1] + m + 1 + d)) - 1; } } } namespace sub3 { void solve (){ vector<array<int, 4>> a(n); for (int i = 0; i < n; i++){ int x, y, z; cin >> x >> y >> z; a[i] = {x + y + z, x + y - z, x - y + z, x - y - z}; } sort(a.begin(), a.end()); int l = 0, r = -1; for (int i = 0; i < n; i++){ while(r + 1 < n && a[r + 1][0] - a[i][0] <= d){ r++; bit.upd(a[r][1] + 2 * m + 1, a[r][2] + 2 * m + 1, a[r][3] + 2 * m + 1, 1); } while(l < n && a[i][0] - a[l][0] > d){ bit.upd(a[l][1] + 2 * m + 1, a[l][2] + 2 * m + 1, a[l][3] + 2 * m + 1, -1); l++; } ans += bit.query(max(1ll, a[i][1] + 2 * m + 1 - d), min(4 * m + 1, a[i][1] + 2 * m + 1 + d), max(1ll, a[i][2] + 2 * m + 1 - d), min(4 * m + 1, a[i][2] + 2 * m + 1 + d), max(1ll, a[i][3] + 2 * m + 1 - d), min(4 * m + 1, a[i][3] + 2 * m + 1 + d) ) - 1; } } } void solve(){ cin >> b >> n >> d >> m; if (b == 1) sub1::solve(); else if (b == 2) sub2::solve(); else if (b == 3) sub3::solve(); cout << ans / 2; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...