oj.uz

Submission #401601

# Submission time Handle Problem Language Result Execution time Memory
401601 2021-05-10T14:41:34 Z Jasiekstrz Ideal city (IOI12_city) C++17
100 / 100
 55 ms 17112 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
const int MOD=1e9;
struct Node
{
	long long id;
	long long l,r;
	long long x;
};
pair<long long,long long> t[NN+10];
vector<Node> tab;
vector<int> e[NN+10];
vector<long long> w[NN+10];
vector<long long> siz[NN+10];
void mknode(int l,int r)
{
	//cerr<<"Node"<<tab.size()<<": x="<<t[l].fi<<" l="<<t[l].se<<" r="<<t[r].se<<"\n";
	w[tab.size()].resize(r-l+1);
	siz[tab.size()].resize(r-l+1);
	tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi});
	return;
}
long long merge(int x,int y) // merge y to x
{
	//cerr<<"merge Node"<<y<<" to Node"<<x<<": ";
	long long ans=0;
	int bi=max(0LL,tab[y].l-tab[x].l),bj=max(0LL,tab[x].l-tab[y].l);
	int ei=bi+min(w[x].size()-bi,w[y].size()-bj),ej=bj+min(w[x].size()-bi,w[y].size()-bj);
	//cerr<<"bi="<<bi<<" ei="<<ei<<" bj="<<bj<<" ej="<<ej<<" ";
	for(int i=0;i<bj;i++)
	{
		w[y][i+1]=(w[y][i+1]+siz[y][i]+w[y][i])%MOD;
		siz[y][i+1]=(siz[y][i+1]+siz[y][i])%MOD;
	}
	for(int i=w[y].size()-1;i>=ej;i--)
	{
		w[y][i-1]=(w[y][i-1]+siz[y][i]+w[y][i])%MOD;
		siz[y][i-1]=(siz[y][i-1]+siz[y][i])%MOD;
	}
	// whole y is in x
	long long p=0,s=0,ps=0,ss=0;
	for(int i=0;i<bi;i++)
	{
		p=(p+ps+w[x][i])%MOD;
		ps=(ps+siz[x][i])%MOD;
	}
	for(int i=w[x].size()-1;i>=ei;i--)
	{
		s=(s+ss+w[x][i])%MOD;
		ss=(ss+siz[x][i])%MOD;
	}
	for(int i=bi,j=bj;i<ei && j<ej;i++,j++)
	{
		p=(p+ps+w[x][i])%MOD;
		ps=(ps+siz[x][i])%MOD;
		ans=(ans+p*siz[y][j]+w[y][j]*ps+ps*siz[y][j])%MOD;
	}
	for(int i=ei-1,j=ej-1;i>=bi && j>=bj;i--,j--)
	{
		s=(s+ss)%MOD;
		ans=(ans+s*siz[y][j]+w[y][j]*ss+ss*siz[y][j])%MOD;
		s=(s+w[x][i])%MOD;
		ss=(ss+siz[x][i])%MOD;
	}
	for(int i=bi,j=bj;i<ei && j<ej;i++,j++)
	{
		siz[x][i]=(siz[x][i]+siz[y][j])%MOD;
		w[x][i]=(w[x][i]+w[y][j]+siz[y][j])%MOD;
	}
	//for(int i=0;i<w[x].size();i++)
	//	cerr<<"ww["<<i<<"]="<<w[x][i]<<" ss["<<i<<"]="<<siz[x][i]<<" ";
	//cerr<<"ans="<<ans<<"\n";
	return ans;
}
long long dfs(int x,int p)
{
	long long ans=0;
	long long tmp=0;
	for(int i=tab[x].l;i<=tab[x].r;i++)
	{
		tmp=(tmp+i-tab[x].l)%MOD;
		ans=(ans+tmp)%MOD;
	}
	fill(w[x].begin(),w[x].end(),0);
	fill(siz[x].begin(),siz[x].end(),1);
	for(auto v:e[x])
	{
		if(v==p)
			continue;
		ans+=dfs(v,x);
		ans+=merge(x,v);
		ans%=MOD;
	}
	return ans;
}
int DistanceSum(int N,int *X,int *Y)
{
	int n=N;
	for(int i=0;i<n;i++)
		t[i+1]={X[i],Y[i]};
	sort(t+1,t+n+1);
	int bg=1;
	for(int i=1;i<=n;i++)
	{
		if(i!=1 && (t[i-1].fi!=t[i].fi || t[i-1].se+1!=t[i].se))
		{
			mknode(bg,i-1);
			bg=i;
		}
	}
	mknode(bg,n);
	int m=tab.size();
	for(int i=0,j=0;i<m;i++)
	{
		while(j<m && tab[j].x<tab[i].x && (tab[j].x<tab[i].x-1 || tab[j].r<tab[i].l))
			j++;
		while(j<m && tab[j].x==tab[i].x-1 && tab[j].l<=tab[i].r)
		{
			//cerr<<"link Node"<<i<<" Node"<<j<<"\n";
			e[i].push_back(j);
			e[j].push_back(i);
			j++;
		}
		if(j>0)
			j--;
		//cerr<<"after "<<i<<" "<<j<<"\n";
	}
	long long ans=dfs(0,-1);
	return (ans+MOD)%MOD;
}

Compilation message

city.cpp: In function 'void mknode(int, int)':
city.cpp:23:25: warning: narrowing conversion of 'tab.std::vector<Node>::size()' from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   23 |  tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi});
      |                 ~~~~~~~~^~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7360 KB Output is correct
3 Correct 6 ms 7376 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7496 KB Output is correct
6 Correct 6 ms 7504 KB Output is correct
7 Correct 6 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7368 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8376 KB Output is correct
2 Correct 11 ms 8396 KB Output is correct
3 Correct 22 ms 9788 KB Output is correct
4 Correct 26 ms 9832 KB Output is correct
5 Correct 39 ms 12196 KB Output is correct
6 Correct 41 ms 12148 KB Output is correct
7 Correct 39 ms 12384 KB Output is correct
8 Correct 40 ms 11972 KB Output is correct
9 Correct 39 ms 12424 KB Output is correct
10 Correct 46 ms 17112 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9076 KB Output is correct
2 Correct 14 ms 8904 KB Output is correct
3 Correct 29 ms 11652 KB Output is correct
4 Correct 31 ms 10940 KB Output is correct
5 Correct 54 ms 15968 KB Output is correct
6 Correct 44 ms 13484 KB Output is correct
7 Correct 55 ms 16136 KB Output is correct
8 Correct 45 ms 13628 KB Output is correct
9 Correct 45 ms 13196 KB Output is correct
10 Correct 50 ms 13096 KB Output is correct