Submission #761118

#TimeUsernameProblemLanguageResultExecution timeMemory
761118NothingXDIdeal city (IOI12_city)C++17
0 / 100
5 ms3156 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...