Submission #288049

#	Time	Username	Problem	Language	Result	Execution time	Memory
288049		erd1	Ideal city (IOI12_city)	C++14	0 / 100	28 ms	2932 KiB

city

#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){
  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) + calcSum(mid, ends);
}

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)':
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;
      |       ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45