oj.uz

Submission #275973

# Submission time Handle Problem Language Result Execution time Memory
275973 2020-08-20T08:43:38 Z 문홍윤(#5111) Circus (Balkan15_CIRCUS) C++17
11 / 100
 360 ms 114936 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];

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];
    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);
        int tmp=lower_bound(arr+1, arr+n, arr[nw]+m-pos)-arr;
        if(tmp<n){
            LL hpos=m+arr[nw]-arr[tmp];
            pq.push(mp(hpos, tmp));
        }
        tmp=upper_bound(arr+1, arr+n, arr[nw]+pos-m)-arr-1;
        if(tmp>=1){
            LL hpos=m-arr[nw]+arr[tmp];
            pq.push(mp(hpos, tmp));
        }
        if(nw>1){
            LL hpos=pos-(arr[nw]-arr[nw-1]);
            pq.push(mp(hpos, nw-1));
        }
        if(nw<n-1){
            LL hpos=pos-(arr[nw+1]-arr[nw]);
            pq.push(mp(hpos, nw+1));
        }
        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);
      |   ~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 44664 KB Output is correct
2 Correct 360 ms 114936 KB Output is correct
3 Correct 274 ms 82192 KB Output is correct
4 Correct 215 ms 47736 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 44664 KB Output is correct
2 Correct 360 ms 114936 KB Output is correct
3 Correct 274 ms 82192 KB Output is correct
4 Correct 215 ms 47736 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 44664 KB Output is correct
2 Correct 360 ms 114936 KB Output is correct
3 Correct 274 ms 82192 KB Output is correct
4 Correct 215 ms 47736 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -