oj.uz

Submission #97509

# Submission time Handle Problem Language Result Execution time Memory
97509 2019-02-16T13:23:17 Z fefe Ideal city (IOI12_city) C++17
0 / 100
 1000 ms 944 KB 
#include<bits/stdc++.h>
#define MAX_N 100005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000000LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
// 1<= N <= 100000
//input N
//input x,y (N)
//output all(x<y)(distance(x,y)) MOD 1000000000
struct node{
	int x,y;
	bool operator < (const node d){
		return (x==d.x)?(y<d.y):(x<d.x);
	};
}V[MAX_N];
int n,ans;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
bool vis[MAX_N];
int get_cnt(int l){
	int r=l;
	while(r+1<n && V[r].x==V[r+1].x && V[r].y+1==V[r+1].y)	r++;
	while(l-1>=0 && V[l-1].x==V[l].x && V[l-1].y+1==V[l].y)	l--;
	for(int i=l;i<=r;i++)	vis[i]=true;
	int z=0,k=0;
	for(int j;j<=r;j++){
		for(int i=0;i<4;i++){
			node p=V[j];
			p.x+=dx[i];
			p.y+=dy[i];
			int idx=lower_bound(V,V+n,p)-V;
			if(p.x!=V[idx].x || p.y!=V[idx].y || vis[idx])	continue;
			int y=get_cnt(idx);
			z+=y;
		}
	}
	k=n-z;
	ans=(int)(((LL)ans+(LL)(z)*(LL)k)%MOD);
	return z+(r-l+1);
}
int DistanceSum(int N, int *X, int *Y) {

 

	int i;
	n=N;
	for(i=0;i<n;i++)	V[i]={X[i],Y[i]};
	V[n]={-1,-1};
	//X
	sort(V,V+n);
	get_cnt(0);
	//Y
	for(i=0;i<n;i++)	swap(V[i].x,V[i].y),vis[i]=false;
	sort(V,V+n);
	get_cnt(0);
	//output ans

	 return ans;

}

Compilation message

city.cpp: In function 'int get_cnt(int)':
city.cpp:46:10: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(int j;j<=r;j++){
          ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1026 ms 944 KB Time limit exceeded
2 Halted 0 ms 0 KB -