oj.uz

Submission #124985

# Submission time Handle Problem Language Result Execution time Memory
124985 2019-07-04T09:31:43 Z nxteru Ideal city (IOI12_city) C++14
100 / 100
 87 ms 22264 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 10 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 9 ms 8188 KB Output is correct
9 Correct 9 ms 8184 KB Output is correct
10 Correct 9 ms 8312 KB Output is correct
11 Correct 9 ms 8184 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Correct 10 ms 8312 KB Output is correct
3 Correct 10 ms 8440 KB Output is correct
4 Correct 10 ms 8448 KB Output is correct
5 Correct 10 ms 8440 KB Output is correct
6 Correct 12 ms 8440 KB Output is correct
7 Correct 10 ms 8444 KB Output is correct
8 Correct 12 ms 8440 KB Output is correct
9 Correct 11 ms 8440 KB Output is correct
10 Correct 10 ms 8444 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 9976 KB Output is correct
2 Correct 21 ms 10104 KB Output is correct
3 Correct 37 ms 13140 KB Output is correct
4 Correct 39 ms 12932 KB Output is correct
5 Correct 68 ms 17784 KB Output is correct
6 Correct 73 ms 17528 KB Output is correct
7 Correct 67 ms 18296 KB Output is correct
8 Correct 76 ms 17684 KB Output is correct
9 Correct 78 ms 17480 KB Output is correct
10 Correct 87 ms 17528 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10872 KB Output is correct
2 Correct 21 ms 11004 KB Output is correct
3 Correct 50 ms 15096 KB Output is correct
4 Correct 39 ms 14500 KB Output is correct
5 Correct 78 ms 21752 KB Output is correct
6 Correct 67 ms 19832 KB Output is correct
7 Correct 81 ms 22264 KB Output is correct
8 Correct 68 ms 19704 KB Output is correct
9 Correct 64 ms 18936 KB Output is correct
10 Correct 64 ms 18808 KB Output is correct