Submission #371605

#	Time	Username	Problem	Language	Result	Execution time	Memory
371605		ja_kingy	Circus (Balkan15_CIRCUS)	C++14	100 / 100	1026 ms	36540 KiB

circus

#include "circus.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> mnstkl,mnstkr;
typedef unsigned int uint;
const int INF = 1e9;

struct ST {
    int sz;
    vector<pii> mn, mn_offset;
    vector<int> lz;
    void pull(int t) {
        mn[t] = min(mn[t*2+1], mn[t*2+2]);
        mn_offset[t] = min(mn_offset[t*2+1], mn_offset[t*2+2]);
    }
    void push(int t) {
        lz[t*2+1] = min(lz[t*2+1], lz[t]);
        lz[t*2+2] = min(lz[t*2+2], lz[t]);
        mn[t*2+1] = min(mn[t*2+1], {mn_offset[t*2+1].first + lz[t], mn_offset[t*2+1].second});
        mn[t*2+2] = min(mn[t*2+2], {mn_offset[t*2+2].first + lz[t], mn_offset[t*2+2].second});
        lz[t] = INF;
    }
    int _qry(int t, int l, int r, int x) {
        if (r - l == 1) return mn[t].first;
        else {
            int m = l+r>>1;
            push(t);
            if (x < m) return _qry(t*2+1, l, m, x);
            else return _qry(t*2+2, m, r, x);
        }
    }
    int qry(int x) { return _qry(0,0,sz,x); }
    void _upd(int t, int l, int r, int x, int v) { 
        if (x <= l) {
            mn[t] = min(mn[t], {mn_offset[t].first + v, mn_offset[t].second});
            lz[t] = min(lz[t], v);
        } else {
            push(t);
            int m = l+r>>1;
            if (x < m) _upd(t*2+1, l, m, x, v);
            _upd(t*2+2, m, r, x, v);
            pull(t);
        }
    }
    void upd(int x, int v) { if (x < sz) _upd(0, 0, sz, x, v); }
    void _set_offset(int t, int l, int r, int x, int v) {
        if (r - l == 1) {
            mn_offset[t] = {v, l};
            mn[t] = {v + INF, l};
        } else {
            int m = l+r>>1;
            push(t);
            if (x < m) _set_offset(t*2+1, l, m, x, v);
            else _set_offset(t*2+2, m, r, x, v);
            pull(t);
        }
    }
    void set_offset(int x, int v) { _set_offset(0, 0, sz, x, v); }
    void init(int N) {
        sz = N;
        mn.resize(4*N, {INF, INF});
        mn_offset.resize(4*N, {INF, INF});
        lz.resize(4*N, INF);
    }
} A, B;

void init(int N, int M, int _P[]){
    vector<int> P(_P, _P+N), bst(N+1);
    P.push_back(M);
    sort(P.begin(), P.end());
    A.init(N+1);
    B.init(N+1);
    for (int i = 0; i < N+1; ++i) {
        A.set_offset(i, P[i]);
        B.set_offset(N-i, M-P[i]);
    }
    A.upd(N, -M);
    for (int i = 0; i < N+1; ++i) {
        pii mn = A.mn[0];
        if (B.mn[0] < mn) {
            mn = {B.mn[0].first, N - B.mn[0].second};
        }
        int x = mn.first + P[mn.second];
        A.upd(lower_bound(P.begin(), P.end(), x) - P.begin(), -P[mn.second]);
        lower_bound(P.rbegin(), P.rend(), x, greater<int>()) - P.rbegin();
        x = P[mn.second] - mn.first;
        B.upd(lower_bound(P.rbegin(), P.rend(), x, greater<int>()) - P.rbegin(), P[mn.second]-M);
        bst[mn.second] = min(A.qry(mn.second), B.qry(N-mn.second));
        A.set_offset(mn.second, INF);
        B.set_offset(N-mn.second, INF);
    }
    priority_queue<pii> pqr;
    for (int i = 0; i < N+1; ++i) pqr.emplace(P[i] - bst[i], P[i]); 
    mnstkr.push_back(pqr.top());
    pqr.pop();
    while (pqr.size()) {
        pii u = pqr.top(); pqr.pop();
        if (u.second < mnstkr.back().second) mnstkr.push_back(u);
    }
    priority_queue<pii, vector<pii>, greater<pii>> pql;
    for (int i = 0; i < N+1; ++i) pql.emplace(P[i] + bst[i], P[i]); 
    mnstkl.push_back(pql.top());
    pql.pop();
    while (pql.size()) {
        pii u = pql.top(); pql.pop();
        if (u.second > mnstkl.back().second) mnstkl.push_back(u);
    }
}

int minLength(int D) {
    int ans = INF;
    auto l = lower_bound(mnstkl.begin(), mnstkl.end(), make_pair(D,INF));
    if (l != mnstkl.begin()) {
        l--;
        ans = min(ans, D - l->second);
    }
    auto r = lower_bound(mnstkr.rbegin(), mnstkr.rend(), make_pair(D,0));
    ans = min(ans, r->second - D);
    return ans;
}

Compilation message (stderr)

circus.cpp: In member function 'int ST::_qry(int, int, int, int)':
circus.cpp:27:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             int m = l+r>>1;
      |                     ~^~
circus.cpp: In member function 'void ST::_upd(int, int, int, int, int)':
circus.cpp:40:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             int m = l+r>>1;
      |                     ~^~
circus.cpp: In member function 'void ST::_set_offset(int, int, int, int, int)':
circus.cpp:52:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |             int m = l+r>>1;
      |                     ~^~
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 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9