| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1090695 |
2024-09-18T15:32:36 Z |
BigBadBully |
Fire (BOI24_fire) |
C++17 |
|
0 ms |
348 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int inf = 1e17;
const int mod = 998244353;
int solve(int n,int m,vector<pii> v)
{
for (int i = 0;i < n; i++)
if (v[i].ff > v[i].ss)
v[i].ss+=m;
sort(v.begin(),v.end());
{
vector<bool> del(n);
int maxi = 0;
for (int i = 0; i < n;i ++)
{
if (v[i].ss <= maxi)
del[i] = 1;
maxi = max(maxi,v[i].ss);
}
vector<pii> neu;
for (int i = 0; i < n; i++)
if (!del[i])
neu.push_back(v[i]);
n = neu.size();
v = neu;
}
{
vector<bool> del(n);
int mini = v[n-1].ss;
for (int i = n-1; i >= 0;i--)
{
if (v[i].ff >= mini)
del[i] = 1;
mini = min(mini,v[i].ff);
}
vector<pii> neu;
for (int i = 0; i < n; i++)
if (!del[i])
neu.push_back(v[i]);
n = neu.size();
v = neu;
}
for (int i = 0; i< n;i++)
v[i].ss%=m;
{
int bigie = 0;
for (int i = 0; i < n; i++)
if (v[i].ff > v[i].ss)
bigie = max(bigie,v[i].ss);
vector<bool> del(n);
for (int i = 0; i < n; i++)
if (v[i].ff < v[i].ss && v[i].ss < bigie)
del[i] = 1;
vector<pii> neu;
for (int i = 0; i < n; i++)
if (!del[i])
neu.push_back(v[i]);
n = neu.size();
v = neu;
}
int oldn = n;
vector<pii> normalni;
for (int i = 0; i < n; i++)
if (v[i].ff < v[i].ss)
normalni.push_back(v[i]);
n = normalni.size();
if (!n)
{
return -1;
}
vector<int> nxt(n);
for (int i = 0; i < n-1; i++)
{
int l = i;
int r = n;
while (r-l>1)
{
int mid = l+r>>1;
if (normalni[mid].ff > normalni[i].ss)
r = mid;
else
l = mid;
}
if (l == i)
{
return -1;
}
nxt[i] = l;
}
nxt[n-1] = -1;
vector<vector<int>> lifts(20,vector<int>(n));
lifts[0] = nxt;
for (int j = 1; j < 20; j++)
for (int i = 0; i < n; i++)
{
if (lifts[j-1][i] == -1)
lifts[j][i] = -1;
else
lifts[j][i] = lifts[j-1][lifts[j-1][i]];
}
n = oldn;
int normala = normalni.size();
int mini= inf;
for (int fix = 0; fix < n; fix++)
{
int f = v[fix].ff, s = v[fix].ss;
int beg;
if (v[fix].ff > v[fix].ss)
{
int L = 0, R = normala-1;
while (R-L>1)
{
int mid = L+R>>1;
if (normalni[mid].ff > s)
R = mid;
else
L = mid;
}
if (normalni[R].ff <= s)
beg = R;
else
beg = L;
int cur = beg;
if (normalni[cur].ff > s)
continue;
int mask = 0;
for (int bit = 19; bit >= 0; bit--)
{
int cand = lifts[bit][cur];
if (cand != -1 && normalni[cand].ss < f)
{
cur = cand;
mask|=(1<<bit);
}
}
if (nxt[cur] != -1)
{
cur = nxt[cur];
mask++;
}
if (normalni[cur].ss < f)
continue;
mini = min(mask+2,mini);
}
}
int lb = 0,rb = inf;
for (int i = 0;i < n; i++)
if (v[i].ff > v[i].ss)
{
lb = max(lb,v[i].ss);
rb = min(rb,v[i].ff);
}
int used = 2;
int maxright = lb;
if (rb >= lb)
mini = min(mini,used);
for (int i = 0; i < n; i++)
{
if (v[i].ff > maxright)
{
used++;
if (i-1 < 0)
{
break;
}
maxright = v[i-1].ss;
if (v[i].ff > maxright)
{
break;
}
if (maxright >= rb)
{
mini = min(used,mini);
}
}
}
if (mini == inf)
return -1;
else
return mini;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
vector<pii> v(n);
for (int i = 0; i < n; i++)
cin >> v[i].ff >> v[i].ss;
cout << solve(n,m,v) << endl;
}
Compilation message
Main.cpp: In function 'long long int solve(long long int, long long int, std::vector<std::pair<long long int, long long int> >)':
Main.cpp:91:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid = l+r>>1;
| ~^~
Main.cpp:129:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
129 | int mid = L+R>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
