Submission #430816

#TimeUsernameProblemLanguageResultExecution timeMemory
430816MarcoMeijerIdeal city (IOI12_city)C++14
100 / 100
157 ms15940 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const vector<T>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);} template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } template<class H> void OUTLS(const H& h) {OUTL(h); } template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); } const ll MOD = 1e9; const int dx[] = {0,1,0,-1}; const int dy[] = {1,0,-1,0}; const int MX = 1e5+10; const int N = 1<<17; struct maxSeg { int seg[N*2], laz[N*2]; void build(int p=1, int l=0, int r=N-1) { seg[p] = -1; laz[p] = -N; if(l == r) return; int m = (l+r)/2; build(p*2,l,m); build(p*2+1,m+1,r); } void setVertex(int p, int v) { seg[p] = v; laz[p] = v; } void push(int p) { if(laz[p] == -N) return; setVertex(p*2,laz[p]); setVertex(p*2+1,laz[p]); laz[p] = -N; } void set(int i, int j, int v, int p=1, int l=0, int r=N-1) { if(j < l || i > r) return; if(i <= l && j >= r) { setVertex(p,v); return; } push(p); int m=(l+r)/2; set(i,j,v,p*2 ,l ,m); set(i,j,v,p*2+1,m+1,r); seg[p] = max(seg[p*2], seg[p*2+1]); } int get(int i, int j, int p=1, int l=0, int r=N-1) { if(j < l || i > r) return -1; if(i <= l && j >= r) return seg[p]; push(p); int m=(l+r)/2; int a=get(i,j,p*2,l,m); if(a != -1) return a; return get(i,j,p*2+1,m+1,r); } } seg; vi atY[MX]; int w[MX], nodes; int L[MX], R[MX]; vi adj[MX]; int n; ll res; void dfs(int u, int p) { FOR(v,adj[u]) { if(v == p) continue; dfs(v,u); w[u] += w[v]; res += ll(n-w[v]) * (ll)w[v]; res %= MOD; } } int DistanceSum(int N, int *X, int *Y) { n=N; // coördinate compression int minX, minY; minX = minY = 1<<31-1; RE(i,n) minX=min(minX,X[i]), minY=min(minY,Y[i]); RE(i,n) X[i]-=minX-1, Y[i]-=minY-1; res = 0; RE(_,2) { // reset graph RE(i,nodes) w[i] = 0; RE(i,nodes) adj[i].clear(); nodes = 0; // fill atY RE(i,MX) atY[i].clear(); RE(i,n) atY[Y[i]].pb(X[i]); RE(i,MX) sort(all(atY[i])); RE(i,MX) atY[i].pb(INF); seg.build(); RE(i,MX) { int nodesCopy = nodes; // link the nodes int lastX = -INF, groupSize = 0; FOR(x,atY[i]) { if(lastX + 1 != x && groupSize != 0) { // new group int l = lastX - groupSize + 1; int r = lastX; int u = nodes++; vi changed; while(true) { int v = seg.get(l,r); if(v == -1) break; adj[u].pb(v); adj[v].pb(u); seg.set(L[v],R[v],-1); changed.pb(v); } FOR(v,changed) seg.set(L[v],R[v],v); w[u] = groupSize; groupSize = 0; } lastX = x; groupSize++; } // update the segment tree seg.set(0,N-1,-1); lastX = -INF, groupSize = 0; FOR(x,atY[i]) { if(lastX + 1 != x && groupSize != 0) { // new group int l = lastX - groupSize + 1; int r = lastX; int u = nodesCopy++; seg.set(l,r,u); L[u] = l, R[u] = r; groupSize = 0; } lastX = x; groupSize++; } } dfs(0,0); swap(X,Y); } return res; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:118:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  118 |     minX = minY = 1<<31-1;
      |                      ~~^~
city.cpp:15:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   15 | #define REP(a,b,c) for(int a=int(b); a<int(c); a++)
      |                    ^~~
city.cpp:16:17: note: in expansion of macro 'REP'
   16 | #define RE(a,c) REP(a,0,c)
      |                 ^~~
city.cpp:127:9: note: in expansion of macro 'RE'
  127 |         RE(i,nodes) adj[i].clear(); nodes = 0;
      |         ^~
city.cpp:127:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  127 |         RE(i,nodes) adj[i].clear(); nodes = 0;
      |                                     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...