oj.uz

Submission #1018634

# Submission time Handle Problem Language Result Execution time Memory
1018634 2024-07-10T07:43:13 Z pcc Ideal city (IOI12_city) C++17
55 / 100
 102 ms 8048 KB 
#include <bits/stdc++.h>
using namespace std;


#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define _all(T) T.begin(),T.end()
#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const ll mod = 1e9;
const int mxn = 1e5+10;
vector<int> paths[mxn];
vector<pii> v;
int N;

ll mad(ll a,ll b){
	assert(a>=0&&b>=0);
	a %= mod;
	a += b;
	return a>=mod?a%mod:a;
}
ll mub(int a,int b){
	assert(a>=0&&b>=0);
	return mad(a,mod-b%mod);
}

namespace SUB1{
	int dist[mxn];
	queue<int> q;
	int BFS(int now){
		memset(dist,-1,sizeof(dist));
		dist[now] = 0;
		q.push(now);
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto nxt:paths[now]){
				if(dist[nxt] == -1){
					dist[nxt] = dist[now]+1;
					q.push(nxt);
				}
			}
		}
		int re = 0;
		for(int i = 0;i<N;i++)re = (re+dist[i])%mod;
		return re;
	}
	int GO(int NN,int* xx,int *yy){
		N = NN;

		for(int i = 0;i<N;i++){
			v.push_back(pii(xx[i],yy[i]));
		}
		vector<int> perm;
		for(int i = 0;i<N;i++)perm.push_back(i);
		sort(perm.begin(),perm.end(),[](int a,int b){return v[a].fs == v[b].fs?v[a].sc<v[b].sc:v[a].fs<v[b].fs;});
		for(int i = 1;i<N;i++){
			int now = perm[i],pre = perm[i-1];
			if(v[now].fs == v[pre].fs&&v[now].sc == v[pre].sc+1){
				paths[now].push_back(pre);
				paths[pre].push_back(now);
			}
		}
		sort(perm.begin(),perm.end(),[](int a,int b){return v[a].sc == v[b].sc?v[a].fs<v[b].fs:v[a].sc<v[b].sc;});
		for(int i = 1;i<N;i++){
			int now = perm[i],pre = perm[i-1];
			if(v[now].sc == v[pre].sc&&v[now].fs == v[pre].fs+1){
				paths[now].push_back(pre);
				paths[pre].push_back(now);
			}
		}
		int ans = 0;
		for(int i = 0;i<N;i++){
			ans += BFS(i);
			ans %= mod;
		}
		assert(ans%2 == 0);
		return ans>>1;
	}
}

namespace SUB2{
	vector<ll> allx,ally;
	struct BIT{
		ll bit[mxn];
		BIT(){}
		void init(){
			for(auto &i:bit)i = 0;
			return;
		}
		void modify(int p,int v){
			for(;p<mxn;p+=p&-p)bit[p] += v;
		}
		ll getval(int s,int e = -1){
			if(e<s)swap(s,e);
			ll re = 0;
			for(;e>0;e-= e&-e)re += bit[e];
			s--;
			for(;s>0;s-= s&-s)re -= bit[s];
			return re;
		}
	};
	BIT sbit,cbit;
	int GO(int NN,int *X,int *Y){
		ll ans = 0;
		N = NN;
		allx.push_back(-1);ally.push_back(-1);
		for(int i = 0;i<N;i++){
			v.push_back(pii(X[i],Y[i]));
			allx.push_back(X[i]);
			ally.push_back(Y[i]);
		}
		sort(_all(allx));sort(_all(ally));
		allx.resize(unique(_all(allx))-allx.begin());
		ally.resize(unique(_all(ally))-ally.begin());

	for(auto &i:v)i.fs = lower_bound(_all(allx),i.fs)-allx.begin(),i.sc = lower_bound(_all(ally),i.sc)-ally.begin();

		sbit.init();cbit.init();
		for(auto &i:v){
			ll cnt1 = cbit.getval(0,i.fs),cnt2 = cbit.getval(i.fs,mxn-1);
			ans += sbit.getval(i.fs,mxn-1)-cnt2*allx[i.fs]+allx[i.fs]*cnt1-sbit.getval(0,i.fs);
			ans %= mod;
			cbit.modify(i.fs,1);
			sbit.modify(i.fs,allx[i.fs]);
		}

		sbit.init();cbit.init();
		for(auto &i:v){
			ll cnt1 = cbit.getval(0,i.sc),cnt2 = cbit.getval(i.sc,mxn-1);
			ans += sbit.getval(i.sc,mxn-1)-cnt2*ally[i.sc]+ally[i.sc]*cnt1-sbit.getval(0,i.sc);
			ans %= mod;
			cbit.modify(i.sc,1);
			sbit.modify(i.sc,ally[i.sc]);
		}
		return ans;

	}
}

int DistanceSum(int N, int *X, int *Y) {
	if(N<=2000)return SUB1::GO(N,X,Y);
	else return SUB2::GO(N,X,Y);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4440 KB Output is correct
2 Correct 21 ms 4440 KB Output is correct
3 Correct 45 ms 4444 KB Output is correct
4 Correct 45 ms 4444 KB Output is correct
5 Correct 71 ms 4696 KB Output is correct
6 Correct 76 ms 4696 KB Output is correct
7 Correct 102 ms 4700 KB Output is correct
8 Correct 74 ms 4696 KB Output is correct
9 Correct 92 ms 4696 KB Output is correct
10 Correct 68 ms 4696 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5596 KB Output is correct
2 Correct 11 ms 5540 KB Output is correct
3 Correct 21 ms 6488 KB Output is correct
4 Correct 21 ms 6348 KB Output is correct
5 Correct 43 ms 7924 KB Output is correct
6 Correct 42 ms 7872 KB Output is correct
7 Correct 44 ms 7928 KB Output is correct
8 Correct 48 ms 7872 KB Output is correct
9 Correct 42 ms 7936 KB Output is correct
10 Correct 43 ms 8048 KB Output is correct

Subtask #4
0 / 45.0

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