| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 275980 |
2020-08-20T08:50:31 Z |
문홍윤(#5111) |
Circus (Balkan15_CIRCUS) |
C++17 |
|
306 ms |
38124 KB |
#include "circus.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;
int n;
LL m, arr[100010];
struct SEGMENT_TREE{
struct NODE{
LL b;
NODE *l, *r;
NODE(){b=0; l=r=0;}
}*rt;
SEGMENT_TREE(){rt=new NODE();}
void update(NODE* nd, LL s, LL e, LL a, LL b, LL val){
if(e<a||s>b)return;
if(a<=s&&e<=b){
nd->b=max(nd->b, val);
return;
}
if(!nd->l)nd->l=new NODE();
if(!nd->r)nd->r=new NODE();
update(nd->l, s, (s+e)/2, a, b , val);
update(nd->r, (s+e)/2+1, e, a, b, val);
}
void update(LL a, LL b, LL val){update(rt, 0ll, m, a, b, val);}
LL query(NODE* nd, LL s, LL e, LL num){
LL ret=nd->b;
if(num<=(s+e)/2&&nd->l)ret=max(ret, query(nd->l, s, (s+e)/2, num));
if(num>(s+e)/2&&nd->r)ret=max(ret, query(nd->r, (s+e)/2+1, e, num));
return ret;
}
LL query(LL num){return query(rt, 0ll, m, num);}
}seg, seg2;
priority_queue<pli> pq;
bool ch[100010];
set<pli> s;
void init(int N, int M, int P[]){
n=N; m=(LL)M;
for(int i=0; i<n; i++)arr[i+1]=(LL)P[i];
for(int i=1; i<=n; i++)s.insert(mp(arr[i], i));
arr[++n]=m;
sort(arr+1, arr+n+1);
pq.push(mp(arr[n-1], n-1));
while(!pq.empty()){
LL pos=pq.top().F; int nw=pq.top().S;
pq.pop();
if(ch[nw])continue;
ch[nw]=true;
//LL temp=max(seg.query(arr[nw])+arr[nw], seg2.query(arr[nw])-arr[nw]);
//assert(pos==temp);
auto tmp=s.lower_bound(mp(arr[nw]+m-pos, 0));
if(tmp!=s.end()){
int nxt=tmp->S;
LL hpos=m+arr[nw]-arr[nxt];
pq.push(mp(hpos, nxt));
}
tmp=s.lower_bound(mp(arr[nw]+pos-m-1, llinf));
if(tmp->S!=nw){
int nxt=tmp->S;
LL hpos=m-arr[nw]+arr[nxt];
pq.push(mp(hpos, nxt));
}
auto hr=s.find(mp(arr[nw], nw));
if(hr!=s.begin()){
hr--;
int nxt=hr->S;
LL hpos=pos-(arr[nw]-arr[nxt]);
pq.push(mp(hpos, nxt));
hr++;
}
hr++;
if(hr!=s.end()){
int nxt=hr->S;
LL hpos=pos-(arr[nxt]-arr[nw]);
pq.push(mp(hpos, nxt));
}
s.erase(mp(arr[nw], nw));
seg.update(0ll, arr[nw]+pos-m, m-arr[nw]);
seg2.update(arr[nw]+m-pos, m, m+arr[nw]);
}
}
int minLength(int D){
LL tmp1=seg.query((LL)D), tmp2=seg2.query((LL)D);
return (int)min(m-(LL)D-tmp1, m+(LL)D-tmp2);
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
14 | 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]
16 | 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]
18 | 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]
21 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
23 | scanf("%d", &d);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
38124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
38124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
38124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
