Submission #124944

#	Time	Username	Problem	Language	Result	Execution time	Memory
124944		nxteru	Ideal city (IOI12_city)	C++14	0 / 100	39 ms	26104 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define M 1000000000
#define PB push_back
#define F first
#define S second
struct node{
	ll s;
	map<ll,ll>x;
	vector<ll>y;
	bool l,r;
	node(void){
		x.clear();
		y.clear();
		l=false,r=false;
	}
	ll cm(ll a,ll b,ll c){
		ll res=0;
		/*
		for(auto it=x.begin();it->F<a;it++){
			x[it->F+1]+=it->S;
			res=(res+it->S)%M;
		}
		for(auto it=x.end();1;){
			it--;
			if(it->F==b)break;
			x[it->F-1]+=it->S;
			res=(res+it->S)%M;
		}
		*/
		for(int i=0;i<a;i++){
			y[i+1]+=y[i];
			res=(res+y[i])%M;
		}
		for(int i=y.size()-1;i>b;i--){
			y[i-1]+=y[i];
			res=(res+y[i])%M;
		}
		return res;
	}
	ll clc(void){
		ll res=0,sum=0;
		for(auto it=x.begin();it!=x.end();it++){
			res=(res+sum*(s-sum)%M)%M;
			sum+=it->S;
		}
		sum=0;
		for(int i=0;i<y.size();i++){
			res=(res+sum*(s-sum)%M)%M;
			sum+=y[i];
		}
		return res;
	}
};
struct edge{
	ll v,m,o,l,r;
};
struct T{
	ll a,b,c;
};
ll n,k,ans;
P q[100005];
vector<vector<T>>p;
node t[100005];
vector<edge>g[100005];
void dfs(int v,int par){
	for(int i=0;i<g[v].size();i++){
		ll u=g[v][i].v,m=g[v][i].m,o=g[v][i].o,l=g[v][i].l,r=g[v][i].r;
		if(u==par)continue;
		dfs(u,v);
		ans=(ans+(n-t[u].s)*t[u].cm(l,r,o)%M)%M;
		for(int j=l;j<=r;j++)t[v].x[j]+=t[u].x[j];
		t[v].y[m]+=t[u].y[o];
		t[v].s+=t[u].s;
	}
	ans=(ans+t[v].clc())%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,-1});
		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 a=p[i][j].a,b=p[i][j].b;
			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 v=p[i-1][w].c,l=p[i-1][w].a,r=p[i-1][w].b;
				if(p[i][j].c==-1&&!(a<l&&t[v].l)&&!(r<b&&t[v].r)){
					if(l<a)t[v].l=true;
					if(b<r)t[v].r=true;
					p[i][j].c=v;
					for(int z=a;z<b;z++)t[v].x[z]++;
					t[v].y.PB(b-a+1LL);
					t[v].s+=(b-a+1LL);
				}else{
					if(p[i][j].c==-1){
						p[i][j].c=k;
						for(int z=a;z<b;z++)t[k].x[z]++;
						t[k].y.PB(b-a+1LL);
						t[k].s+=(b-a+1LL);
						k++;
					}
					int u=p[i][j].c;
					g[u].PB(edge{v,t[u].y.size()-1,t[v].y.size()-1,max(a,l),min(b,r)});
					g[v].PB(edge{u,t[v].y.size()-1,t[u].y.size()-1,max(a,l),min(b,r)});
				}
				w++;
			}
			if(p[i][j].c==-1){
				p[i][j].c=k;
				for(int z=a;z<b;z++)t[k].x[z]++;
				t[k].y.PB(b-a+1LL);
				t[k].s+=(b-a+1LL);
				k++;
			}
		}
	}
	dfs(0,-1);
	return ans;
}

Compilation message (stderr)

city.cpp: In member function 'll node::clc()':
city.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<y.size();i++){
               ~^~~~~~~~~
city.cpp: In function 'void dfs(int, int)':
city.cpp:69: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:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++){
              ~^~~~~~~~~
city.cpp:93:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<p[i].size();j++){
               ~^~~~~~~~~~~~
city.cpp:95: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:96: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){
               ~^~~~~~~~~~~~~~
city.cpp:114:34: warning: narrowing conversion of '(t[u].node::y.std::vector<long long int>::size() - 1)' from 'std::vector<long long int>::size_type {aka long unsigned int}' to 'll {aka long long int}' inside { } [-Wnarrowing]
      g[u].PB(edge{v,t[u].y.size()-1,t[v].y.size()-1,max(a,l),min(b,r)});
                     ~~~~~~~~~~~~~^~
city.cpp:114:50: warning: narrowing conversion of '(t[v].node::y.std::vector<long long int>::size() - 1)' from 'std::vector<long long int>::size_type {aka long unsigned int}' to 'll {aka long long int}' inside { } [-Wnarrowing]
      g[u].PB(edge{v,t[u].y.size()-1,t[v].y.size()-1,max(a,l),min(b,r)});
                                     ~~~~~~~~~~~~~^~
city.cpp:115:34: warning: narrowing conversion of '(t[v].node::y.std::vector<long long int>::size() - 1)' from 'std::vector<long long int>::size_type {aka long unsigned int}' to 'll {aka long long int}' inside { } [-Wnarrowing]
      g[v].PB(edge{u,t[v].y.size()-1,t[u].y.size()-1,max(a,l),min(b,r)});
                     ~~~~~~~~~~~~~^~
city.cpp:115:50: warning: narrowing conversion of '(t[u].node::y.std::vector<long long int>::size() - 1)' from 'std::vector<long long int>::size_type {aka long unsigned int}' to 'll {aka long long int}' inside { } [-Wnarrowing]
      g[v].PB(edge{u,t[v].y.size()-1,t[u].y.size()-1,max(a,l),min(b,r)});
                                     ~~~~~~~~~~~~~^~

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