| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 288141 |
2020-09-01T09:02:39 Z |
erd1 |
Ideal city (IOI12_city) |
C++14 |
|
1000 ms |
5748 KB |
#include<bits/stdc++.h>
using namespace std;
/*
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T>
using order_statistics_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define int lld
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
typedef long double ld;
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << "(" << p.ff << ", " << p.ss << ")";
}
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; i++)
out << (i==b?"":" ") << *i;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
return outIt(out << '[', all(v)) << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, map<T1, T2> m){
return outIt(out << '{', all(m)) << '}';
}
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T1, typename T2>
pair<T1, T2>& operator+=(pair<T1, T2>& a, pair<T1, T2> p){
return a.ff += p.ff, a.ss += p.ss, a;
}
typedef vector<pii>::iterator it;
const int mod = 1000000000;
vector<vector<int>> G;
min_heap<pair<int, pii>> q;
vector<bool> gone;
void toX(it begs, it ends, int targ, map<int, pii>& ans){ // points should be sorted;
//outIt(cout << "toX", begs, ends) << " " << targ << endl;
int n = ends-begs;
for(int i = 0; i < n; i++)G[i].resize(0);
for(int i = 0; i < n; i++){
auto pi = begs[i];
auto it1 = lower_bound(begs, ends, (pii){pi.ff+1, pi.ss}), it2 = lower_bound(begs, ends, (pii){pi.ff, pi.ss+1});
if(it1 != ends && *it1 == (pii){pi.ff+1, pi.ss})
G[i].pb(it1-begs), G[it1-begs].pb(i);
if(it2 != ends && *it2 == (pii){pi.ff, pi.ss+1})
G[i].pb(it2-begs), G[it2-begs].pb(i);
if(pi.ff == targ)q.push({0, {i, pi.ss}});
}
//cout << G << endl;
ans.clear();
for(int i = 0; i < n; i++)gone[i] = 0;
while(q.size()){
auto a = q.top(); q.pop();
if(gone[a.ss.ff])continue;
gone[a.ss.ff] = true;
ans[a.ss.ss] += {a.ff, 1};
ans[a.ss.ss].ff%=mod;
//cout << a << endl;
for(auto i: G[a.ss.ff])
if(!gone[i])q.push({a.ff+1, {i, a.ss.ss}});
}
for(int i = 0; i < n; i++)assert(gone[i]);
//cout << ans << endl;
//return ans;
}
map<int, pii> mpa, mpb;
//int ccc = 0;
int calcSum(it begs, it ends, int xl, int xr, int yl, int yr, int ccc = 0){
assert(ccc++ < 100);
//outIt(cout << "calc sum", begs, ends) << " " << make_pair(make_pair(xl, xr), make_pair(yl, yr)) << endl;
//for(auto i = begs; i != ends; i++)assert(i->ff >= xl && i->ff < xr && i->ss >= yl && i->ss < yr);
if(begs == ends)return 0;
if(next(begs) == ends) return 0;
if(next(begs) == prev(ends))return 1;
int n = ends - begs;
sort(begs, ends);
int midx = (xl+xr)/2;
it mid = lower_bound(begs, ends, (pii){midx, INT_MIN});//, mid2 = lower_bound(begs, ends, (pii){midx+1, INT_MIN});
//cout << midx << " " << ends-mid << endl;
//it mid = max(mid1-begs, ends-mid1) > max(mid2-begs, ends-mid2)?mid2:mid1;
lld ans = 0;
if(mid != begs && mid != ends){
//midx = mid->ff;
toX(begs, mid, midx-1, mpa); toX(mid, ends, midx, mpb);
lld acnt = 0, bcnt = 0, asum = 0, bsum = 0, ldis = -1;
for(auto ita = mpa.begin(), itb = mpb.begin(); ita != mpa.end() || itb != mpb.end();){
if(ita == mpa.end() || itb != mpb.end() && *itb < *ita){
//cout << "inb" << *itb << acnt << endl;
(asum += acnt*(itb->ff-ldis))%=mod, (bsum += bcnt*(itb->ff-ldis))%=mod;
(ans += asum*itb->ss.ss%mod + itb->ss.ff*acnt%mod + itb->ss.ss*acnt%mod)%=mod;
(bsum += itb->ss.ff)%=mod, (bcnt += itb->ss.ss)%=mod;
ldis = itb->ff;
++itb;
}else {
(asum += acnt*(ita->ff-ldis))%=mod, (bsum += bcnt*(ita->ff-ldis))%=mod;
(ans += bsum*ita->ss.ss + ita->ss.ff*bcnt + ita->ss.ss*bcnt)%=mod;
(asum += ita->ss.ff)%=mod, (acnt += ita->ss.ss)%=mod;
ldis = ita->ff;
++ita;
}
//cout << acnt << " " << bcnt << " " << ans << endl;
}
}
/*
{
int ansx = 0;
for(auto ax: mpa)
for(auto bx: mpb)
ansx += (abs(ax.ff-bx.ff)+1)*ax.ss.ss*bx.ss.ss + ax.ss.ff*bx.ss.ss + ax.ss.ss*bx.ss.ff;
assert(ansx == ans);
}
*/
//outIt(cout << "calc sum", begs, ends) << " " << ans << endl;
for(auto i = begs; i != ends; i++)swap(i->ff, i->ss);
return (ans + calcSum(begs, mid, yl, yr, xl, midx, ccc) + calcSum(mid, ends, yl, yr, midx, xr, ccc))%mod;
}
int toXY(it begs, it ends, int x, int y){ // points should be sorted;
//outIt(cout << "toX", begs, ends) << " " << targ << endl;
int n = ends-begs;
sort(begs, ends);
for(int i = 0; i < n; i++)G[i].resize(0);
for(int i = 0; i < n; i++){
auto pi = begs[i];
auto it1 = lower_bound(begs, ends, (pii){pi.ff+1, pi.ss}), it2 = lower_bound(begs, ends, (pii){pi.ff, pi.ss+1});
if(it1 != ends && *it1 == (pii){pi.ff+1, pi.ss})
G[i].pb(it1-begs), G[it1-begs].pb(i);
if(it2 != ends && *it2 == (pii){pi.ff, pi.ss+1})
G[i].pb(it2-begs), G[it2-begs].pb(i);
if(pi.ff == x && pi.ss == y)q.push({0, {i, 0}});
}
//cout << G << endl;
int ans = 0;
for(int i = 0; i < n; i++)gone[i] = 0;
while(q.size()){
auto a = q.top(); q.pop();
if(gone[a.ss.ff])continue;
gone[a.ss.ff] = true;
ans += a.ff;
//ans[a.ss.ss].ff%=mod;
//cout << a << endl;
for(auto i: G[a.ss.ff])
if(!gone[i])q.push({a.ff+1, {i, 0}});
}
for(int i = 0; i < n; i++)assert(gone[i]);
//cout << ans << endl;
return ans;
}
vector<pii> v;
signed DistanceSum(signed N, signed *X, signed *Y) {
G.resize(N), gone.resize(N);
for(int i = 0; i < N; i++)v.pb({X[i], Y[i]});
int ans = 0, sumx = 0, sumy = 0;
if(N <= 2000){
for(int i = 0; i < N; i++)
ans += toXY(all(v), X[i], Y[i]);
return (ans/2)%mod;
}
sort(X, X+N); sort(Y, Y+N);
for(int i = 0; i < N; i++){
(ans += ((lld)X[i]*i-sumx)%mod+mod)%=mod;
(ans += ((lld)Y[i]*i-sumy)%mod+mod)%=mod;
(sumx += X[i])%=mod, (sumy += Y[i])%=mod;
}
//cout << ans << endl;
//*/
//int ans2 = calcSum(all(v), 0, INT_MAX, 0, INT_MAX);
//assert(ans == ans2);
return ans%mod;
}
Compilation message
city.cpp: In function 'lld calcSum(it, it, lld, lld, lld, lld, lld)':
city.cpp:108:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
108 | if(ita == mpa.end() || itb != mpb.end() && *itb < *ita){
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
city.cpp:96:7: warning: unused variable 'n' [-Wunused-variable]
96 | int n = ends - begs;
| ^
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:178:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
178 | for(int i = 0; i < N; i++)
| ^~~
city.cpp:180:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
180 | return (ans/2)%mod;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
9 ms |
384 KB |
Output is correct |
| 7 |
Correct |
11 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
384 KB |
Output is correct |
| 9 |
Correct |
11 ms |
384 KB |
Output is correct |
| 10 |
Correct |
13 ms |
384 KB |
Output is correct |
| 11 |
Correct |
12 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
384 KB |
Output is correct |
| 2 |
Correct |
286 ms |
504 KB |
Output is correct |
| 3 |
Correct |
614 ms |
632 KB |
Output is correct |
| 4 |
Correct |
671 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
1099 ms |
512 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1660 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1660 KB |
Output is correct |
| 3 |
Correct |
18 ms |
3064 KB |
Output is correct |
| 4 |
Correct |
17 ms |
3064 KB |
Output is correct |
| 5 |
Correct |
36 ms |
5748 KB |
Output is correct |
| 6 |
Correct |
34 ms |
5748 KB |
Output is correct |
| 7 |
Correct |
39 ms |
5740 KB |
Output is correct |
| 8 |
Correct |
36 ms |
5740 KB |
Output is correct |
| 9 |
Correct |
34 ms |
5740 KB |
Output is correct |
| 10 |
Correct |
34 ms |
5740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
