oj.uz

Submission #1111994

# Submission time Handle Problem Language Result Execution time Memory
1111994 2024-11-13T13:35:03 Z michified Circus (Balkan15_CIRCUS) C++17
11 / 100
 50 ms 5680 KB 
#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

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 50 ms 5456 KB Output is correct
2 Correct 50 ms 5680 KB Output is correct
3 Correct 49 ms 5456 KB Output is correct
4 Correct 48 ms 5456 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5456 KB Output is correct
2 Correct 50 ms 5680 KB Output is correct
3 Correct 49 ms 5456 KB Output is correct
4 Correct 48 ms 5456 KB Output is correct
5 Incorrect 1 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5456 KB Output is correct
2 Correct 50 ms 5680 KB Output is correct
3 Correct 49 ms 5456 KB Output is correct
4 Correct 48 ms 5456 KB Output is correct
5 Incorrect 1 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -