oj.uz

답안 #73300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73300 2018-08-28T06:57:12 Z 노영훈(#2269) Circus (Balkan15_CIRCUS) C++11
49 / 100
 4000 ms 381920 KB 
#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int D[MX], X[MX], n, m;

int lo(int x){ return upper_bound(X, X+n+1, x)-X-1; }
int hi(int x){ return lower_bound(X, X+n+1, x)-X; }

struct seg1_st{
	struct node{
		int r, l, rz, lz, mn;
	} tree[1<<18];
	void init(int v=1, int s=0, int e=n){
	}
	void busy(int v, int s, int e){
	}
	void uptr(int r, int val, int v=1, int s=0, int e=n){
	}
	void uptl(int l, int val, int v=1, int s=0, int e=n){
	}
	int get(int v=1, int s=0, int e=n){
		return 0;
	}
	int val(int pos, int v=1, int s=0, int e=n){
		return 0;
	}
	void erase(int pos, int v=1, int s=0, int e=n){
	}
};


struct seg2_st{
	int A[1<<18], B[1<<18];
	void init(int v=1, int s=0, int e=n){
		if(s==e){ A[v]=X[s]+D[s], B[v]=X[s]-D[s]; return; }
		init(v*2,s,(s+e)/2); init(v*2+1,(s+e)/2+1,e);
		A[v]=min(A[v*2], A[v*2+1]);
		B[v]=max(B[v*2], B[v*2+1]);
	}
	int ub(int r, int val, int v=1, int s=0, int e=n){
		if(A[v]>val) return -1;
		if(s==e) return e;
		int m=(s+e)/2;
		if(m<r){
			int now=ub(r,val,v*2+1,m+1,e);
			if(now>=0) return now;
		}
		return ub(r,val,v*2,s,m);
	}
	int lb(int l, int val, int v=1, int s=0, int e=n){
		if(B[v]<val) return n+1;
		if(s==e) return s;
		int m=(s+e)/2;
		if(l<=m){
			int now=lb(l,val,v*2,s,m);
			if(now<=n) return now;
		}
		return lb(l,val,v*2+1,m+1,e);
	}
} Seg2;

void init(int N, int M, int P[]){
	n=N, m=M;
	for(int i=0; i<n; i++) X[i]=P[i];

	sort(X, X+n); X[n]=m;

/*
	seg1_st Seg1; Seg1.init();

	for(int _=0; _<=n; _++){
		int v=Seg1.get(), d=Seg1.val(v);
		Seg1.erase(v);
		assert(0<=v && v<=n);

		int a=lo(X[v]-d), b=hi(X[v]+d);
		if(0<=a && a<=n) Seg1.uptr(a, X[v]);
		if(0<=b && b<=n) Seg1.uptl(b, X[v]);
	}

	for(int i=0; i<=n; i++) D[i]=Seg1.val(i);
*/


	for(int i=0; i<=n; i++) D[i]=inf;
	D[n]=0;

	vector<pii> G[MX];
	for(int i=0; i<=n; i++) for(int j=i+1; j<=n; j++){
		G[i].push_back({X[j]-X[i], j});
		G[j].push_back({X[j]-X[i], i});
	}

	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({D[n], n});
	while(!Q.empty()){
		int v,d; tie(d,v)=Q.top(); Q.pop();
		for(pii e:G[v]){
			int x,c; tie(c,x)=e;
			if(c<d || D[x]<=c) continue;
			D[x]=c, Q.push({c,x});
		}
	}

//	for(int i=0; i<n; i++) cout<<D[i]<<' ';
//	cout<<'\n';

	Seg2.init();
}

int minLength(int pos){
	int a=lo(pos), b=hi(pos);
	if(a==b) return D[a];
	
	int p=-1, q=-1;

	if(0<=a && a<=n) p=Seg2.ub(a,pos);
	if(0<=b && b<=n) q=Seg2.lb(b,pos);

	int res=inf;
	if(0<=p && p<=n) res=min(res, abs(pos-X[p]));
	if(0<=q && q<=n) res=min(res, abs(pos-X[q]));

	assert(res<inf);

	return res; 
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
  long long max_code;
            ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &P[i]);
   ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4078 ms 381920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 381920 KB Output is correct
2 Correct 6 ms 381920 KB Output is correct
3 Correct 5 ms 381920 KB Output is correct
4 Correct 5 ms 381920 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 381920 KB Output is correct
2 Correct 6 ms 381920 KB Output is correct
3 Correct 5 ms 381920 KB Output is correct
4 Correct 5 ms 381920 KB Output is correct
5 Correct 721 ms 381920 KB Output is correct
6 Correct 944 ms 381920 KB Output is correct
7 Correct 761 ms 381920 KB Output is correct
8 Correct 684 ms 381920 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 381920 KB Output is correct
2 Correct 6 ms 381920 KB Output is correct
3 Correct 5 ms 381920 KB Output is correct
4 Correct 5 ms 381920 KB Output is correct
5 Correct 721 ms 381920 KB Output is correct
6 Correct 944 ms 381920 KB Output is correct
7 Correct 761 ms 381920 KB Output is correct
8 Correct 684 ms 381920 KB Output is correct
9 Correct 1593 ms 381920 KB Output is correct
10 Correct 1599 ms 381920 KB Output is correct
11 Correct 1410 ms 381920 KB Output is correct
12 Correct 1607 ms 381920 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4078 ms 381920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4078 ms 381920 KB Time limit exceeded
2 Halted 0 ms 0 KB -