Submission #124985

#	Time	Username	Problem	Language	Result	Execution time	Memory
124985		nxteru	Ideal city (IOI12_city)	C++14	100 / 100	87 ms	22264 KiB

city

#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.end();i++){
			x[i->F+1]+=i->S;
			res=(res+i->S)%M;
		}
		for(auto i=x.end();1;){
			i--;
			if(i->F<=r||i==x.begin())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!=x.end();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-q)%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});
				if(w+1<p[i-1].size()&&p[i-1][w+1].a<=b)w++;
				else break;
			}
		}
	}
	dfs(0,-1,INF,INF);
	return ans;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int, int, ll, ll)':
city.cpp:55: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:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++){
              ~^~~~~~~~~
city.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<p[i].size();j++){
               ~^~~~~~~~~~~~
city.cpp:82: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:83: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:87:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(w+1<p[i-1].size()&&p[i-1][w+1].a<=b)w++;
        ~~~^~~~~~~~~~~~~~

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