Submission #1201457

#TimeUsernameProblemLanguageResultExecution timeMemory
1201457adiyerPairs (IOI07_pairs)C++20
60 / 100
1202 ms2752 KiB
#pragma optimize ("g",on) #pragma GCC optimize("inline") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("03") #include <bits/stdc++.h> using namespace std; typedef int ll; const int N = 2e5 + 11; ll B, n, k, m; ll a[N], b[N], c[N], t[N]; long long res; vector < ll > v[100][100]; void add(ll i, ll x){ for(; i < N; i += (i & (-i))) t[i] += x; } ll get(ll r){ ll ret = 0; for(; r > 0; r -= (r & (-r))) ret += t[r]; return ret; } ll get(ll l, ll r){ return get(r) - get(l - 1); } void solve(){ cin >> B >> n >> k >> m; if(B == 3){ for(ll i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i], v[a[i]][b[i]].push_back(c[i]); for(ll i = 1; i <= m; i++) for(ll j = 1; j <= m; j++) sort(v[i][j].begin(), v[i][j].end()); for(ll i1 = 1; i1 <= m; i1++){ for(ll j1 = 1; j1 <= m; j1++){ for(ll i2 = 1; i2 <= m; i2++){ for(ll j2 = 1; j2 <= m; j2++){ if(v[i2][j2].empty() || v[i1][j1].empty()) continue; ll d = k - abs(i1 - i2) - abs(j1 - j2); if(d < 0) continue; // cout << d << ' ' << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n'; ll L = 0, R = v[i2][j2].size() - 1; for(ll i = 0; i < v[i1][j1].size(); i++){ while(v[i2][j2][L] < v[i1][j1][i] - d) L++; while(v[i2][j2][R] > v[i1][j1][i] + d) R--; if(i1 == i2 && j1 == j2) R--; res += (R - L + 1); // cout << v[i1][j1][i] << ' ' << R - L + 1 << '\n'; } } } } } cout << res; } else if(B == 1){ for(ll i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); for(ll i = 1; i <= n; i++){ ll L, R, l, r; l = 0, r = n; while(r - l > 1){ ll md = (l + r) / 2; if(a[md] + k >= a[i]) r = md; else l = md; } L = r; l = 0, r = n + 1; while(r - l > 1){ ll md = (l + r) / 2; if(a[md] - k <= a[i]) l = md; else r = md; } R = l; res += (R - L + 1); // cout << i << ' ' << L << ' ' << R << '\n'; } cout << (res - n) / 2; } else{ vector < pair < ll, ll > > scan; for(ll i = 1; i <= n; i++) cin >> a[i] >> b[i]; for(ll i = 1; i <= n; i++) scan.push_back({a[i] - b[i], a[i] + b[i]}); sort(scan.begin(), scan.end()); ll j = 0; for(auto x : scan){ while(x.first - scan[j].first > k) add(scan[j].second, -1), j++; res += get(x.second - k, x.second + k), add(x.second, 1); } cout << res; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) 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...
#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...