#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()
#define print(a) \
for (auto &x : a) \
cout << x << " "; \
cout << endl;
#define printmp(a) \
for (auto &x : a) \
cout << x.fs << " " << x.ss << endl;
const int mod = 998244353;
struct SegmentTree
{
vector<int> tree;
int size;
int merge(int a, int b)
{
return a + b;
}
int single()
{
return 1e9;
}
void init(int n)
{
size = 1;
while (size < n)
size *= 2;
tree.resize(2 * size, 1e9);
}
void build(int n, int x, int lx, int rx)
{
if (rx - lx == 1)
{
tree[x] = single();
return;
}
int m = (lx + rx) / 2;
build(n, 2 * x + 1, lx, m);
build(n, 2 * x + 2, m, rx);
tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
}
void build(int n)
{
build(n, 0, 0, size);
}
void set(int l, int r, int v, int x, int lx, int rx)
{
if (l <= lx and rx <= r)
{
tree[x] = min(tree[x], v);
return;
}
if (rx <= l or r <= lx)
return;
int m = (lx + rx) / 2;
set(l, r, v, 2 * x + 1, lx, m);
set(l, r, v, 2 * x + 2, m, rx);
}
void set(int l, int r, int v)
{
set(l, r, v, 0, 0, size);
}
int sum(int i, int s, int x, int lx, int rx)
{
s = min(s, tree[x]);
if (rx - lx == 1)
return s;
int m = (lx + rx) / 2;
if (i < m)
s = sum(i, s, 2 * x + 1, lx, m);
else
s = sum(i, s, 2 * x + 2, m, rx);
return s;
}
int sum(int i)
{
return sum(i, 1e9, 0, 0, size);
}
};
void solve(){
int n;
cin >> n;
vector<pair<int, int>> a(n);
for(int i = 0; i < n; i ++)
cin >> a[i].fs >> a[i].ss;
int q;
cin >> q;
for(int i = 0; i < q; i ++){
int x;
cin >> x;
SegmentTree s;
s.init(n);
int l = x, r = x, mxl = a[x - 1].fs, mxr = a[x - 1].ss;
s.set(x - 1, x, 0);
int ans = 0;
while(mxl <= l or r <= mxr){
int left = (l < mxl ? 1e9 : s.sum(l - 1)), right = (r > mxr ? 1e9 : s.sum(r - 1));
if(r > mxr or (mxl <= l and left <= right)){
s.set(a[l - 1].fs - 1, a[l - 1].ss, left + 1);
mxl = min(mxl, a[l - 1].fs);
mxr = max(mxr, a[l - 1].ss);
l --;
}
else{
s.set(a[r - 1].fs - 1, a[r - 1].ss, right + 1);
mxl = min(mxl, a[r - 1].fs);
mxr = max(mxr, a[r - 1].ss);
r ++;
}
}
for(int i = 1; i <= n; i ++)
ans = max(ans, s.sum(i - 1));
if(l == 0 and r == n + 1)
cout << ans << endl;
else
cout << -1 << endl;
}
}
signed main()
{
// fastio
int t = 1;
// cin >> t;
while (t--)
{
solve();
// cout << endl;
}
}
Compilation message
passport.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
2 | #pragma gcc optimize("Ofast")
|
passport.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization("Ofast")
|
passport.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
4 | #pragma optimize(Ofast)
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
148 ms |
7592 KB |
Output is correct |
| 5 |
Correct |
129 ms |
7508 KB |
Output is correct |
| 6 |
Correct |
118 ms |
7668 KB |
Output is correct |
| 7 |
Correct |
95 ms |
7764 KB |
Output is correct |
| 8 |
Correct |
72 ms |
6976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
148 ms |
7592 KB |
Output is correct |
| 5 |
Correct |
129 ms |
7508 KB |
Output is correct |
| 6 |
Correct |
118 ms |
7668 KB |
Output is correct |
| 7 |
Correct |
95 ms |
7764 KB |
Output is correct |
| 8 |
Correct |
72 ms |
6976 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
