| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 73404 |
2018-08-28T08:27:39 Z |
노영훈(#2269) |
Circus (Balkan15_CIRCUS) |
C++11 |
|
4000 ms |
371212 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 shit(){
int E[MX];
for(int i=0; i<=n; i++) E[i]=inf;
E[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({E[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 || E[x]<=c) continue;
E[x]=c, Q.push({c,x});
}
}
for(int i=0; i<=n; i++) if(E[i]!=D[i]) exit(i);
}
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);
}
shit();
/*
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 |
Execution timed out |
4066 ms |
371212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
371212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
371212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
371212 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4066 ms |
371212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4066 ms |
371212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
