Submission #288058

#TimeUsernameProblemLanguageResultExecution timeMemory
288058erd1Ideal city (IOI12_city)C++14
0 / 100
27 ms3068 KiB
#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 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; 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}; //cout << a << endl; for(auto i: G[a.ss.ff]) if(!gone[i])q.push({a.ff+1, {i, a.ss.ss}}); } //cout << ans << endl; //return ans; } map<int, pii> mpa, mpb; //int ccc = 0; int calcSum(it begs, it ends, int ccc = 0){ assert(ccc++ < 100); if(begs == ends)return 0; if(next(begs) == ends) return 0; int n = ends - begs; sort(begs, ends); int midx = (prev(ends)->ff-begs->ff)/2; it mid1 = lower_bound(begs, ends, (pii){midx, INT_MIN}), mid2 = lower_bound(begs, ends, (pii){midx+1, INT_MIN}); it mid = max(mid1-begs, ends-mid1) > max(mid2-begs, ends-mid2)?mid2:mid1; int ans = 0; if(mid != begs && mid != ends){ midx = mid->ff; toX(begs, mid, midx-1, mpa); toX(mid, ends, midx, mpb); int 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), bsum += bcnt*(itb->ff-ldis); ans += asum*itb->ss.ss + itb->ss.ff*acnt + itb->ss.ss*acnt; bsum += itb->ss.ff, bcnt += itb->ss.ss; ldis = itb->ff; ++itb; }else { asum += acnt*(ita->ff-ldis), bsum += bcnt*(ita->ff-ldis); ans += bsum*ita->ss.ss + ita->ss.ff*bcnt + ita->ss.ss*bcnt; asum += ita->ss.ff, acnt += ita->ss.ss; 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, ccc) + calcSum(mid, ends, ccc); } vector<pii> v; int DistanceSum(int N, int *X, int *Y) { G.resize(N), gone.resize(N); for(int i = 0; i < N; i++)v.pb({X[i], Y[i]}); return calcSum(all(v)); return N; }

Compilation message (stderr)

city.cpp: In function 'int calcSum(it, it, int)':
city.cpp:100:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  100 |       if(ita == mpa.end() || itb != mpb.end() && *itb < *ita){
      |                              ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
city.cpp:89:7: warning: unused variable 'n' [-Wunused-variable]
   89 |   int n = ends - begs;
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...