이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
const int B = 1 << 17;
int n, m, k, q, s, t, a, b;
pair<int, int> seg[17][B * 2];
vector<int> v[2][NMAX];
multiset<int> ms;
pair<int, int> operator /(const pair<int, int>& a, const pair<int, int>& b){
return {min(a.first, b.first), max(a.second, b.second)};
}
void pull(int t){
for(int i = B - 1; i; i--) seg[t][i] = seg[t][i * 2] / seg[t][i * 2 + 1];
}
pair<int,int> qry(int t, int l, int r){
l += B; r += B;
pair<int, int> p = {n + 1, 0};
while(l <= r){
if(l & 1) p = p / seg[t][l++];
if(!(r & 1)) p = p / seg[t][r--];
l /= 2; r /= 2;
}
return p;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k >> m;
while(m--){
cin >> a >> b;
if(a < b){
v[0][a].emplace_back(b);
v[0][min(a + k, b)].emplace_back(-b);
}
else{
v[1][a].emplace_back(b);
v[1][max(a - k, b)].emplace_back(-b);
}
}
for(int i = 0; i < 17; i++)
for(int j = 1; j < B * 2; j++) seg[i][j] = {n + 1, 0};
for(int t = 0; t < 2; t++){
multiset<int> ms;
if(!t){
for(int i = 1; i <= n; i++){
for(int& x : v[t][i]){
if(x > 0) ms.emplace(x);
else ms.erase(ms.find(-x));
}
seg[0][B + i].second = (ms.empty() ? i : *ms.rbegin());
}
}
else{
for(int i = n; i; i--){
for(int& x : v[t][i]){
if(x > 0) ms.emplace(x);
else ms.erase(ms.find(-x));
}
seg[0][B + i].first = (ms.empty() ? i : *ms.begin());
}
}
}
pull(0);
for(int i = 1; i < 17; i++){
for(int j = 1; j <= n; j++)
seg[i][B + j] = qry(i - 1, seg[i - 1][B + j].first, seg[i - 1][B + j].second);
pull(i);
}
cin >> q;
while(q--){
cin >> s >> t;
int l = s, r = s, cur = 0;
for(int i = 16; i >= 0; i--){
auto [mn, mx] = qry(i, l, r);
if(t < mn || t > mx){
cur += 1 << i;
l = mn, r = mx;
}
}
if(++cur == (1 << 17)) cout << "-1\n";
else cout << cur << '\n';
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:84:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | auto [mn, mx] = qry(i, l, r);
| ^
# | 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... |