Submission #124978

#TimeUsernameProblemLanguageResultExecution timeMemory
124978nxteruIdeal city (IOI12_city)C++14
0 / 100
1092 ms10872 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; #define INF (1LL<<31)-1LL #define M 1000000000 #define PB push_back #define F first #define S second struct node{ ll s; map<ll,ll>x; node(void){ s=0; x.clear(); } ll cm(ll l,ll r){ ll res=0; for(auto i=x.begin();i->F!=l;i++){ x[i->F+1]+=i->S; res=(res+i->S)%M; } for(auto i=x.end();1;){ i--; if(i->F==r)break; x[i->F-1]+=i->S; res=(res+i->S)%M; } return res; } ll clc(ll l,ll r){ ll res=0,p=0,q=0; for(auto i=x.begin();i->F<l;i++){ p+=i->S; res=(res+p*(s-p)%M)%M; } for(auto i=x.end();1;){ i--; if(i->F<=r||i==x.begin())break; q+=i->S; res=(res+q*(s-p-q)%M)%M; } res=(res+p*q%M*(r-l+1LL)%M)%M; return res; } }; struct T{ ll a,b,c; }; ll n,k,ans; P q[100005]; node t[100005]; vector<vector<T>>p; vector<T>g[100005]; void dfs(int v,int par,ll pl,ll pr){ for(int i=0;i<g[v].size();i++){ ll u=g[v][i].a,l=g[v][i].b,r=g[v][i].c; if(u==par)continue; dfs(u,v,l,r); ans=(ans+(n-t[u].s)*(t[u].cm(l,r)+t[u].s)%M)%M; for(int j=l;j<=r;j++)t[v].x[j]+=t[u].x[j]; t[v].s+=t[u].s; } ans=(ans+t[v].clc(pl,pr))%M; } int DistanceSum(int N, int *X, int *Y) { n=N; for(int i=0;i<n;i++)q[i]=P(Y[i],X[i]); sort(q,q+n); vector<T>o; o.clear(); for(int i=0;i<n;i++){ if(i==0||q[i-1].F!=q[i].F)p.PB(o); if(p.back().size()==0||p.back().back().b!=q[i].S-1)p.back().PB(T{q[i].S,q[i].S,k++}); else p.back().back().b++; } for(int i=0;i<p.size();i++){ int w=0; for(int j=0;j<p[i].size();j++){ ll v=p[i][j].c,a=p[i][j].a,b=p[i][j].b; t[v].s=b-a+1LL; for(int z=a;z<=b;z++)t[v].x[z]++; while(i>0&&w<p[i-1].size()&&p[i-1][w].b<a)w++; while(i>0&&w<p[i-1].size()&&p[i-1][w].a<=b){ ll u=p[i-1][w].c,l=max(p[i-1][w].a,a),r=min(p[i-1][w].b,b); g[v].PB(T{u,l,r}); g[u].PB(T{v,l,r}); w++; } } } dfs(0,-1,INF,INF); return ans; }

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int, ll, ll)':
city.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++){
              ~^~~~~~~~~
city.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<p[i].size();j++){
               ~^~~~~~~~~~~~
city.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i>0&&w<p[i-1].size()&&p[i-1][w].b<a)w++;
               ~^~~~~~~~~~~~~~
city.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i>0&&w<p[i-1].size()&&p[i-1][w].a<=b){
               ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...