| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 993203 |
2024-06-05T12:38:59 Z |
vladilius |
Fire (BOI24_fire) |
C++17 |
|
2000 ms |
348 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 2e9 + 5;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("ain1.txt", "r", stdin);
int n, m; cin>>n>>m;
vector<int> log(n + 1);
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
vector<int> l(n + 1), r(n + 1);
vector<pii> all = {{-1, -1}};
bool ind = 1;
for (int i = 1; i <= n; i++){
cin>>l[i]>>r[i];
if (!r[i]) r[i] = m;
else r[i]--;
if (l[i] > r[i]){
r[i] += m;
ind = 0;
}
all.pb({l[i], r[i]});
}
sort(all.begin() + 1, all.end());
if (ind){
int x = 0, i = 1, out = 0;
while (i <= n && x <= m){
int mx = -1;
while (i <= n && all[i].ff <= x){
mx = max(mx, all[i].ss);
}
if (mx == -1){
cout<<-1<<"\n";
return 0;
}
out++;
x = mx + 1;
}
if (x > m) cout<<out<<"\n";
else cout<<-1<<"\n";
return 0;
}
vector<pii> nw = {{-1, -1}};
int i = 1;
while (i <= n){
int j = i;
while (j <= n && all[i].ff == all[j].ff) j++;
nw.pb(all[j - 1]);
i = j;
}
all = nw;
n = all.size() - 1;
auto cmp = [&](pii x, pii y){
if (x.ss == y.ss) return x.ff < y.ff;
return x.ss < y.ss;
};
sort(all.begin() + 1, all.end(), cmp);
nw.clear();
nw.pb({-1, -1});
i = 1;
while (i <= n){
int j = i;
while (j <= n && all[i].ss == all[j].ss) j++;
nw.pb(all[i]);
i = j;
}
all = nw;
n = all.size() - 1;
sort(all.begin() + 1, all.end());
int lg = ceil(log2(n));
vector<vector<pii>> sp(n + 1, vector<pii>(lg + 1));
for (int i = 1; i <= n; i++){
sp[i][0] = {all[i].ss, i};
}
for (int t = 1; t <= lg; t++){
for (int i = 1; i + (1 << t) <= n + 1; i++){
sp[i][t] = max(sp[i][t - 1], sp[i + (1 << (t - 1))][t - 1]);
}
}
auto get_max = [&](int l, int r){
int t = log[r - l + 1];
return max(sp[l][t], sp[r - (1 << t) + 1][t]);
};
vector<int> ff;
for (int i = 1; i <= n; i++) ff.pb(all[i].ff);
vector<int> :: iterator it1, it2;
vector<int> g(n + 1);
for (int i = 1; i <= n; i++){
int l = all[i].ff, r = all[i].ss + 1;
it1 = lower_bound(ff.begin(), ff.end(), l);
it2 = upper_bound(ff.begin(), ff.end(), r);
int u = (it1 - ff.begin()) + 1, v = (it2 - ff.begin());
pii b = get_max(u, v);
if (b.ff >= r) g[i] = b.ss;
}
vector<int> x(n + 1);
x[0] = inf;
for (int i = 1; i <= n; i++){
x[i] = all[i].ss + 1;
}
vector<vector<int>> pw(n + 1, vector<int>(lg + 1)), mx(n + 1, vector<int>(lg + 1));
vector<bool> used(n + 1);
used[0] = 1;
function<void(int)> fill = [&](int v){
if (used[v]) return;
fill(g[v]);
used[v] = 1;
pw[v][0] = g[v];
mx[v][0] = x[g[v]];
for (int i = 1; i <= lg; i++){
pw[v][i] = pw[pw[v][i - 1]][i - 1];
mx[v][i] = max(mx[v][i - 1], mx[pw[v][i - 1]][i - 1]);
}
};
for (int i = 1; i <= n; i++){
fill(i);
}
auto get = [&](int v, int k){
int ans = x[v];
for (int i = lg; i >= 0; i--){
if (k >= (1 << i)){
k -= (1 << i);
ans = max(ans, mx[v][i]);
v = pw[v][i];
}
}
return ans;
};
int out = n + 1;
for (int i = 1; i <= n; i++){
int lm = all[i].ff + m;
int lb = 0, rb = n - 1;
while (lb + 1 < rb){
int m = (lb + rb) / 2;
int v = get(i, m);
if (v >= lm){
rb = m;
}
else {
lb = m + 1;
}
}
if (get(i, rb) < lm) continue;
if (get(i, lb) >= lm) rb = lb;
if (get(i, rb) != inf) out = min(out, rb + 1);
}
if (out == n + 1) cout<<-1<<"\n";
else cout<<out<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Execution timed out |
2099 ms |
348 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Execution timed out |
2099 ms |
348 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Execution timed out |
2099 ms |
348 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
2079 ms |
348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
2055 ms |
348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Execution timed out |
2099 ms |
348 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
