#include <bits/stdc++.h>
using namespace std;
#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
/*
at most 1 is going to work overnight
n^3 sol:
dp[l][r] = minimum number from the left bound of l's to the right bound of r's
how will we sort them - just by left bound?
or i guess you start at a left bound and iterate over the right bounds
are we gonna assume we're using l and r? not necessarily sometimes the overlap
and you can just use 1 instead
if r ends before l ends
then you want to find the bounds for each r-value
which i guess you can do by sorting or smth
is 5000^2log too much for binary search & sorting
if no one works overnight
then we're also confined to a single possible starting point at 0
so if we can do that in n^2log we can do this in nlog
if all the intervals have the same length
then ???
also if B is entirely contained in A
then you would never ever use A
*/
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
function<int(int, int)> dist = [&] (int x, int y) {
if (y > x) return y - x;
return y + m - x;
};
vector<array<int, 2>> a(n);
bool good = true;
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
if (a[i][1] == 0) a[i][1] = m;
if (a[i][1] < a[i][0]) good = false;
}
sort(a.begin(), a.end(), [&] (array<int, 2> a1, array<int, 2> a2) {
return a1[0] < a2[0] || (a1[0] == a2[0] && dist(a1[0], a1[1]) < dist(a2[0], a2[1]));
});
vector<array<int, 2>> na;
for (int i = 0; i < n; i++) {
if (na.size() && na.back()[0] == a[i][0]) na.pop_back();
na.push_back(a[i]);
}
a = na;
n = (int) a.size();
parr2d(a);
if (good && a[0][0] != 0) {
cout << -1 << '\n';
} else {
// note: this means you have to use a[i]
int ans = 1e9;
for (int i = 0; i < n; i++) {
pv(i);
vector<array<int, 3>> b(n);
for (int j = 0; j < n; j++) {
b[j] = {a[j][0], a[j][1], j};
}
swap(b[0], b[i]);
sort(b.begin() + 1, b.end(), [&] (array<int, 3> a1, array<int, 3> a2) {
return dist(a[i][1], a1[1]) < dist(a[i][1], a2[1]);
});
vector<int> ord(n);
for (int j = 0; j < n; j++) {
ord[b[j][2]] = j;
}
parr2d(b);
vector<int> at(n);
int pos = 0;
for (int it = 1; it < n; it++) {
int val = a[(i + it) % n][0]; pv(val);
while (pos < n && dist(b[0][0], b[pos][1]) < dist(b[0][0], val)) {
pv(pos); pv(dist(b[0][0], b[pos][1])); pv(dist(b[0][0], val));
pos++;
}
at[ord[(i + it) % n]] = pos;
}
parr(at);
vector<int> dp(n); // dp[j] = min segments needed so that i is 1st & j is lst
dp[0] = 1;
vector<int> st(1, 0); // suffix minima
for (int j = 1; j < n; j++) {
int lb = lower_bound(st.begin(), st.end(), at[j]) - st.begin();
if (lb < st.size()) {
dp[j] = dp[st[lb]] + 1;
while (dp[st.back()] >= dp[j]) st.pop_back();
st.push_back(j);
} else {
dp[j] = 1e9;
}
if (dist(b[0][0], b[j][1]) >= m) {
pv(j);
ans = min(ans, dp[j]);
}
}
parr(dp);
}
cout << (ans == 1e9 ? -1 : ans) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |