Submission #1111994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111994		michified	Circus (Balkan15_CIRCUS)	C++17	11 / 100	50 ms	5680 KiB

circus

#include <bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define imx INT_MAX
#define imn INT_MIN
#define lmx LLONG_MAX
#define lmn LLONG_MIN
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
#define ordered_llset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> 

int n, m;
vector<int> st, lazy;

void pd(int id, int l, int mid, int r) {
    st[lid] = min(st[lid], lazy[id]);
    st[rid] = min(st[rid], lazy[id]);
    lazy[lid] = min(lazy[lid], lazy[id]);
    lazy[rid] = min(lazy[rid], lazy[id]);
    lazy[id] = m;
}

int query(int id, int l, int r, int pos) {
    if (l == r) return st[id];
    int mid = (l + r) / 2;
    pd(id, l, mid, r);
    if (pos <= mid) return query(lid, l, mid, pos);
    return query(rid, mid + 1, r, pos);
}

void upd(int id, int l, int r, int ur, int val) {
    if (ur < l) return;
    if (r <= ur) {
        st[id] = min(st[id], val);
        lazy[id] = min(lazy[id], val);
        return;
    }
    int mid = (l + r) / 2;
    pd(id, l, mid, r);
    upd(lid, l, mid, ur, val);
    upd(rid, mid + 1, r, ur, val);
    st[id] = min(st[lid], st[rid]);
}

vector<int> thres, pos;

void init(int N, int M, int p[]) {
    n = N;
    m = M;
    if (n == 0) return;
    st.resize(n * 4, m);
    lazy.resize(n * 4, m);
    sort(p, p + n);
    pos.resize(n);
    int i, cur;
    for (i = 0; i < n; i++) pos[i] = p[i];
    thres.resize(n);
    upd(0, 0, n - 1, n, m);
    for (i = n - 1; i >= 0; i--) {
        cur = query(0, 0, n - 1, i);
        thres[i] = cur - pos[i];
        upd(0, 0, n - 1, upper_bound(pos.begin(), pos.end(), pos[i] - thres[i]) - pos.begin() - 1, pos[i]);
        thres[i] = pos[i] - thres[i];
    }
    for (i = 1; i < n; i++) thres[i] = max(thres[i], thres[i - 1]);
}

int minLength(int d) {
    int tmp = lower_bound(thres.begin(), thres.end(), d) - thres.begin();
    if (tmp == n) return m - d;
    return pos[tmp] - d;
}

Compilation message (stderr)

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: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9