oj.uz

답안 #73403

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

inline int _min(int x, int y){ return x<y ? x : y; }
inline int _max(int x, int y){ return x>y ? x : y; }
int _min(int a, int b, int c){ return _min(a,_min(b,c)); }

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 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;

	vector<int> R[MX];

	for(int i=n, r=n; i>=0; i--){
		for(int j:R[i]) r=min(r, j);
		D[i]=X[r]-X[i];
		assert(D[i]>=0);
		int a=lo(X[i]-D[i]);
		if(0<=a) R[a].push_back(i);
	}
/*	
	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
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 7416 KB Output is correct
2 Correct 56 ms 7524 KB Output is correct
3 Correct 53 ms 7524 KB Output is correct
4 Correct 51 ms 7600 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 7416 KB Output is correct
2 Correct 56 ms 7524 KB Output is correct
3 Correct 53 ms 7524 KB Output is correct
4 Correct 51 ms 7600 KB Output is correct
5 Incorrect 4 ms 7600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 7416 KB Output is correct
2 Correct 56 ms 7524 KB Output is correct
3 Correct 53 ms 7524 KB Output is correct
4 Correct 51 ms 7600 KB Output is correct
5 Incorrect 4 ms 7600 KB Output isn't correct
6 Halted 0 ms 0 KB -