#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <unistd.h>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#endif
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp << " " <<
#define F(i, s, n) for(int i = s; i < (int) n; i++)
#define pb push_back
#define fi first
#define se second
int mod = 1e9+7;
int inf = 1e6;
const int N = 3e5;
int t[N];
template<typename T> struct bit2d {
vector<T> bit;
vi xs;
vi st;
vi cnt;
int n, alllen;
void init(int N, vpi Q) {
n = N;
cnt.assign(N+1, 0);
st.resize(N+1);
sort(Q.begin(), Q.end(), [](pii &a, pii &b) { return a.se > b.se; });
F(i, 0, Q.size()) {
for(int j = Q[i].fi; j > 0 && j < N; j += (j & -j)) cnt[j]++;
}
st[0] = cnt[0]+1;
F(i, 1, N) {
st[i] = st[i-1] + cnt[i];
}
alllen = st[N-1];
xs.assign(alllen+3, 0);
bit.assign(alllen+3, 0);
F(i, 0, Q.size()) {
for(int j = Q[i].fi; j > 0 && j < N; j += (j & -j)) xs[--st[j]] = Q[i].se;
}
}
int find(int y, int el) {
return upper_bound(xs.begin() + st[y], xs.begin() + st[y] + cnt[y], el) - xs.begin() - st[y];
}
void update(int y, int x, T el) {
while(y > 0 && y < n) {
//cout << y sp x sp find(y, x) sp cnt[y] << endl;
for(int i = find(y, x); i > 0 && i <= cnt[y]; i += (i & -i)) {
//cout << y sp i << endl;
bit[i + st[y]] += el;
}
y += (y & -y);
}
}
T query(int y, int x) {
T res = T();
while(y > 0 && y < n) {
//cout << y sp x sp find(y, x) sp cnt[y] << endl;
for(int i = find(y, x); i > 0 && i <= cnt[y]; i -= (i & -i)) {
//cout << y sp i << endl;
res += bit[i + st[y]];
}
y -= (y & -y);
}
return res;
}
};
void solve() {
int d, n, k, m;
cin >> d >> n >> k >> m;
if(d == 1) {
vi a(n);
F(i, 0, n) cin >> a[i];
sort(a.begin(), a.end());
queue<int> last;
int ans = 0;
F(i, 0, n) {
while(last.size() && last.front() < a[i] - k) last.pop();
ans += last.size();
last.push(a[i]);
}
cout << ans << endl;
} else if(d == 2) {
vpi a(n);
F(i, 0, n) cin >> a[i].fi >> a[i].se;
F(i, 0, n) {
int y = a[i].fi, x = a[i].se;
a[i].fi = x - y;
a[i].se = x + y;
}
sort(a.begin(), a.end());
Tree<pii> st;
int ans = 0;
queue<int> q;
F(i, 0, n) {
while(q.size() && a[q.front()].fi < a[i].fi - k) {
st.erase({a[q.front()].se, q.front()});
q.pop();
}
ans += st.order_of_key({a[i].se + k, inf}) - st.order_of_key({a[i].se - k, -1});
st.insert({a[i].se, i});
q.push(i);
}
cout << ans << endl;
} else if(d == 3) {
vector<pair<int, pii>> a(n);
F(i, 0, n) {
cin >> a[i].se.fi >> a[i].se.se >> a[i].fi;
int y = a[i].se.fi, x = a[i].se.se;
a[i].se.fi = x + y;
a[i].se.se = x - y + m;
}
sort(a.begin(), a.end());
vpi Q;
F(i, 0, n) Q.pb({a[i].se.fi, a[i].se.se});
bit2d<int> bit[305];
F(i, 0, 305) bit[i].init(4*m, Q);
int ans = 0;
queue<int> q;
F(i, 0, n) {
//while(q.size() && a[q.front()].fi < a[i].fi - )
F(z, 0, 305) {
int nk = k - abs(z - a[i].fi);
if(nk < 0) continue;
ans += bit[z].query(a[i].se.fi + nk, a[i].se.se + nk) - bit[z].query(a[i].se.fi + nk, a[i].se.se - nk - 1) - bit[z].query(a[i].se.fi - nk - 1, a[i].se.se + nk) + bit[z].query(a[i].se.fi - nk - 1, a[i].se.se - nk - 1);
}
q.push(i);
bit[a[i].fi].update(a[i].se.fi, a[i].se.se, 1);
}
cout << ans << endl;
}
}
void setIO() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Local
freopen("local.in", "r", stdin);
freopen("local.out", "w", stdout);
#else
// freopen("friendcross.in","r",stdin);
// freopen("friendcross.out","w",stdout);
#endif
}
signed main() {
setIO();
int t = 1;
//cin >> t;
while(t--) solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
500 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
15 ms |
2140 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
2304 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
2044 KB |
Output is correct |
| 2 |
Correct |
17 ms |
2148 KB |
Output is correct |
| 3 |
Correct |
16 ms |
2184 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
46 ms |
2956 KB |
Output is correct |
| 2 |
Correct |
61 ms |
9280 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
75 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
103 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
88 ms |
5460 KB |
Output is correct |
| 4 |
Correct |
86 ms |
5904 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
83 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
95 ms |
7020 KB |
Output is correct |
| 3 |
Correct |
68 ms |
6664 KB |
Output is correct |
| 4 |
Correct |
77 ms |
6372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
61 ms |
27608 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
27360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
772 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
777 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
692 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
