oj.uz

Submission #121856

# Submission time Handle Problem Language Result Execution time Memory
121856 2019-06-27T06:53:45 Z baluteshih Ideal city (IOI12_city) C++14
55 / 100
 107 ms 7692 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},ans;
const ll MOD=1e9;
vector<ll> G[100005];
vector<pll> v;
bitset<100005> vis;
unordered_map<ll,ll> mp;

void DQ(ll l,ll r)
{
	if(l==r) return;
	ll m=l+r>>1,a,b,sum=0,rsum=0;
	DQ(l,m),DQ(m+1,r);
	queue<pll> q;
	for(a=l;a<=m;++a)
		sum=(sum+v[a].F+v[a].S)%MOD;
	for(a=l,b=m+1;a<=m&&b<=r;)
		if(v[a].S>=v[b].S)
			sum=(sum-v[a].F%MOD-v[a].S%MOD+MOD+MOD)%MOD,rsum=(rsum+v[a].F-v[a].S%MOD+MOD)%MOD,q.push(v[a++]);
		else
			ans=(ans+(v[b].F+v[b].S)*(m-a+1)+(v[b].F-v[b].S)*(a-l)-sum+MOD-rsum+MOD)%MOD,q.push(v[b++]);
	while(a<=m)
		q.push(v[a++]);
	while(b<=r)
		ans=(ans+(v[b].F+v[b].S)*(m-a+1)+(v[b].F-v[b].S)*(a-l)-sum+MOD-rsum+MOD)%MOD,q.push(v[b++]);
	for(int i=l;i<=r;++i)
		v[i]=q.front(),q.pop();	
}

int DistanceSum(int N, int *X, int *Y)
{
	if(N<=2000)
	{
		for(int i=0;i<N;++i)
			mp[(ll)X[i]<<31|Y[i]]=i;
		for(int i=0;i<N;++i)
			for(int j=0;j<4;++j)
			{
				auto p=mp.find(((ll)(X[i]+dx[j])<<31)|(Y[i]+dy[j]));
				if(p!=mp.end()) G[i].pb(p->S);
			}
		for(int i=0;i<N;++i)
		{
			int tp=0;
			queue<pii> q;
			q.push(MP(i,0)),vis.reset(),vis[i]=1;
			while(!q.empty())
			{
				auto tmp=q.front();
				q.pop(),ans=(ans+tmp.S)%MOD,vis[tmp.F]=1;
				for(int j:G[tmp.F])
					if(!vis[j]) q.push(MP(j,tmp.S+1)),vis[j]=1;
				++tp;
			}
		}
		ans/=2;
	}
	else
	{
		for(int i=0;i<N;++i)
			v.pb(MP((ll)X[i],(ll)Y[i]));
		sort(ALL(v)),DQ(0,N-1);
	}
	return ans;
}

Compilation message

city.cpp: In function 'void DQ(ll, ll)':
city.cpp:26:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1,a,b,sum=0,rsum=0;
       ~^~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2716 KB Output is correct
2 Correct 30 ms 2864 KB Output is correct
3 Correct 61 ms 2860 KB Output is correct
4 Correct 66 ms 2880 KB Output is correct
5 Correct 107 ms 2944 KB Output is correct
6 Correct 93 ms 2924 KB Output is correct
7 Correct 106 ms 2916 KB Output is correct
8 Correct 95 ms 2924 KB Output is correct
9 Correct 94 ms 2944 KB Output is correct
10 Correct 89 ms 2920 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3580 KB Output is correct
2 Correct 16 ms 3560 KB Output is correct
3 Correct 35 ms 4736 KB Output is correct
4 Correct 36 ms 4724 KB Output is correct
5 Correct 71 ms 6672 KB Output is correct
6 Correct 71 ms 7360 KB Output is correct
7 Correct 74 ms 7692 KB Output is correct
8 Correct 70 ms 7404 KB Output is correct
9 Correct 78 ms 7404 KB Output is correct
10 Correct 70 ms 7532 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3580 KB Output isn't correct
2 Halted 0 ms 0 KB -