| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 594146 | Bobaa | Golf (JOI17_golf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 100;
const int inf = 2e9 + 100;
const int mod = 1e9 + 7;
struct segtree {
bool v;
int l, r;
};
segtree p[maxn * 50];
int cnt;
int create() {
return cnt++;
}
int build(int l, int r) {
int t = create();
if (l == r) return t;
int m = (l + r) / 2;
p[t].l = build(l, m);
p[t].r = build(m + 1, r);
return t;
}
int upd(int cur, int l, int r, int id, int w) {
int t = create();
if (l == r) {
p[t].v = w;
return t;
}
int m = (l + r) / 2;
if (id <= m) {
p[t].l = upd(p[cur].l, l, m, id, w);
p[t].r = p[cur].r;
} else {
p[t].l = p[cur].l;
p[t].r = upd(p[cur].r, m + 1, r, id, w);
}
p[t].v = (p[p[t].l].v | p[p[t].r].v);
return t;
}
void get(int t, int tl, int tr, int l, int r, vector<int> &h) {
if (l > r || !p[t].v) return;
if (tl == tr) {
h.push_back(l);
p[t].v = 0;
return;
}
int m = (tl + tr) / 2;
get(p[t].l, tl, m, l, min(r, m), h);
get(p[t].r, m + 1, tr, max(l, m + 1), r, h);
p[t].v = (p[p[t].l].v | p[p[t].r].v);
}
pair<int, int> strt, fin;
int n;
pair<pair<int, int>, pair<int, int>> rec[maxn];
map<int, int> mpik;
vector<int> srt;
vector<pair<int, pair<int, int>>> seg[2];
int d[maxn];
int q[maxn];
pair<int, int> bo[maxn];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> strt.first >> strt.second >> fin.first >> fin.second;
cin >> n;
for (int i = 0; i < n; i++) cin >> rec[i].first.first >> rec[i].first.second >> rec[i].second.first >> rec[i].second.second;
for (int t = 0; t < 2; t++) {
vector<pair<int, pair<int, int>>> que;
for (int i = 0; i < n; i++) {
que.push_back(make_pair(rec[i].second.first, rec[i].first));
que.push_back(make_pair(rec[i].second.second, rec[i].first));
que.push_back(make_pair(rec[i].second.first, make_pair(inf, rec[i].first.first)));
que.push_back(make_pair(rec[i].second.first, make_pair(inf, rec[i].first.second)));
que.push_back(make_pair(rec[i].second.second, make_pair(-inf, rec[i].first.first)));
que.push_back(make_pair(rec[i].second.second, make_pair(-inf, rec[i].first.second)));
swap(rec[i].first, rec[i].second);
}
que.push_back(make_pair(strt.second, make_pair(strt.first, strt.first)));
que.push_back(make_pair(fin.second, make_pair(fin.first, fin.first)));
swap(strt.first, strt.second);
swap(fin.first, fin.second);
sort(que.begin(), que.end());
set<int> st;
st.insert(-1);
st.insert(inf);
for (auto its : que) {
if (its.second.first == -inf) st.erase(its.second.second);
else {
if (its.second.first == inf) st.insert(its.second.second);
else {
set<int>::iterator it = st.upper_bound(its.second.first);
it--;
int le = *it;
it = st.lower_bound(its.second.second);
seg[t].push_back(make_pair(its.first, make_pair(le, *it)));
}
}
}
sort(seg[t].begin(), seg[t].end());
seg[t].resize(unique(seg[t].begin(), seg[t].end()) - seg[t].begin());
}
n = seg[0].size() + seg[1].size();
assert(n < maxn);
for (int t = 0; t < 2; t++) {
for (int i = 0; i < seg[t].size(); i++) {
int l = lower_bound(seg[!t].begin(), seg[!t].end(), make_pair(seg[t][i].second.first, make_pair(-inf, -inf))) - seg[!t].begin();
int r = upper_bound(seg[!t].begin(), seg[!t].end(), make_pair(seg[t][i].second.second, make_pair(inf, inf))) - seg[!t].begin() - 1;
if (!t) {
l += seg[0].size();
r += seg[0].size();
}
bo[i + t * seg[0].size()] = make_pair(l, r);
}
vector<pair<int, pair<int, int>>> que;
for (int i = 0; i < seg[t].size(); i++) que.push_back(make_pair(seg[t][i].first, make_pair(i + t * seg[0].size(), 0)));
for (int i = 0; i < seg[!t].size(); i++) {
que.push_back(make_pair(seg[!t][i].second.first, make_pair(-inf, i + !t * seg[0].size())));
que.push_back(make_pair(seg[!t][i].second.second, make_pair(inf, i + !t * seg[0].size())));
}
sort(que.begin(), que.end());
int cur = build(0, n - 1);
for (auto its : que) {
if (its.second.first == inf) cur = upd(cur, 0, n - 1, its.second.second, 1);
else {
if (its.second.first == inf) cur = upd(cur, 0, n - 1, its.second.second, 0);
else q[its.second.first] = cur;
}
}
}
for (int i = 0; i < n; i++) d[i] = -1;
int sta, stb, fina, finb;
for (int i = 0; i < seg[0].size(); i++) if (seg[0][i].first == strt.second && seg[0][i].second.first <= strt.first && seg[0][i].second.second >= strt.first) sta = i;
for (int i = 0; i < seg[1].size(); i++) if (seg[1][i].first == strt.first && seg[1][i].second.first <= strt.second && seg[1][i].second.second >= strt.second) stb = seg[0].size() + i;
for (int i = 0; i < seg[0].size(); i++) if (seg[0][i].first == fin.second && seg[0][i].second.first <= fin.first && seg[0][i].second.second >= fin.first) fina = i;
for (int i = 0; i < seg[1].size(); i++) if (seg[1][i].first == fin.first && seg[1][i].second.first <= fin.second && seg[1][i].second.second >= fin.second); finb = seg[0].size() + i;
d[sta] = 0;
d[stb] = 0;
queue<int> que;
que.push(sta);
que.push(stb);
while (!que.empty()) {
int id = que.front();
que.pop();
if (id == fina || id == finb) {
cout << d[id] + 1;
return 0;
}
vector<int> g;
get(q[id], 0, n - 1, bo[id].first, bo[id].second, g);
for (int i : g) if (d[i] == -1) {
d[i] = d[id] + 1;
que.push(i);
}
}
return 0;
}