# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
73375 |
2018-08-28T08:00:13 Z |
노영훈(#2269) |
Circus (Balkan15_CIRCUS) |
C++11 |
|
62 ms |
7688 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> Q[MX];
for(int i=n, r=n; i>=0; i--){
for(int x:Q[i]) r=min(r, x);
D[i]=X[r]-X[i];
int a=lo(X[i]-D[i]);
if(0<=a) Q[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);
~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
7420 KB |
Output is correct |
2 |
Correct |
55 ms |
7496 KB |
Output is correct |
3 |
Correct |
57 ms |
7636 KB |
Output is correct |
4 |
Correct |
55 ms |
7688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
7688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
7688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
7688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
7420 KB |
Output is correct |
2 |
Correct |
55 ms |
7496 KB |
Output is correct |
3 |
Correct |
57 ms |
7636 KB |
Output is correct |
4 |
Correct |
55 ms |
7688 KB |
Output is correct |
5 |
Incorrect |
6 ms |
7688 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
7420 KB |
Output is correct |
2 |
Correct |
55 ms |
7496 KB |
Output is correct |
3 |
Correct |
57 ms |
7636 KB |
Output is correct |
4 |
Correct |
55 ms |
7688 KB |
Output is correct |
5 |
Incorrect |
6 ms |
7688 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |