#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;
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];
}
}
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);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
5476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
5476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
5476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
