#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename H, typename... T>
void debug_out(H h, T... t){
cerr << h << ' ';
debug_out(t...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e5 + 10;
const int inf = 2147483647;
const int mod = 1e9;
int add(int x, int y){
int res = x + y;
if (res >= mod) return res - mod;
if (res < 0) return res + mod;
return res;
}
int n, x[maxn], y[maxn], cnt[maxn], dis[maxn];
vector<int> val[maxn];
int DistanceSum(int N, int *X, int *Y) {
n = N;
int mnx = inf, mny = inf, mx = 0;
for (int i = 1; i <= n; i++){
x[i] = X[i-1];
y[i] = Y[i-1];
mnx = min(mnx, x[i]);
mny = min(mny, y[i]);
mx = max(mx, x[i]);
}
mnx--;
mny--;
for (int i = 1; i <= n; i++){
x[i] -= mnx;
y[i] -= mny;
val[x[i]].push_back(y[i]);
}
int ans = 0;
for (int i = 1; i <= mx-mnx; i++){
sort(all(val[i]));
int l = val[i][0], r = val[i].back();
if (i > 1){
for (auto x: val[i-1]){
if (l <= x && x <= r){
dis[x] = add(dis[x], cnt[x]);
}
}
for (auto x: val[i-1]){
if (x < l){
cnt[l] += cnt[x];
dis[l] = add(dis[l], 1ll * cnt[x] * (l - x + 1) % mod);
dis[l] = add(dis[l], dis[x]);
cnt[x] = 0;
dis[x] = 0;
}
else if (x > r){
cnt[r] += cnt[x];
dis[r] = add(dis[r], 1ll * cnt[x] * (x - r + 1) % mod);
dis[r] = add(dis[r], dis[x]);
cnt[x] = 0;
dis[x] = 0;
}
}
}
int sumcnt = 0, sumdis = 0;
for (auto x: val[i]){
sumdis = add(sumdis, add(dis[x], sumcnt));
ans = add(ans, sumdis);
sumcnt = add(sumcnt, cnt[x]);
}
reverse(all(val[i]));
sumcnt = sumdis = 0;
for (auto x: val[i]){
sumdis = add(sumdis, sumcnt);
ans = add(ans, sumdis);
sumdis = add(sumdis, dis[x]);
sumcnt = add(sumcnt, cnt[x]);
}
reverse(all(val[i]));
for (auto x: val[i]){
cnt[x]++;
}
int tmp = val[i].size();
ans = add(ans, 1ll * tmp * (tmp-1) / 2 % mod);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
