| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122464 |
2019-06-28T11:10:21 Z |
egorlifar |
Golf (JOI17_golf) |
C++17 |
|
89 ms |
55392 KB |
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <chrono>
using namespace std;
template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) {
if (x > y) {
x = y;
return 1;
}
else {
return 0;
}
}
template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) {
if (x < y) {
x = y;
return 1;
}
else {
return 0;
}
}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
#define read(FILENAME) freopen((string(FILENAME) + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((string(FILENAME) + ".out").c_str(), "w", stdout);
template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
while (begin != end) {
out << (*begin) << " ";
begin++;
}
out << endl;
}
template<class T> void output(const T &x, ostream &out = cerr) {
output(x.begin(), x.end(), out);
}
void fast_io() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
const int MAXN = 100228;
int s, t, u, v;
int n;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
vector<int> vx;
vector<int> vy;
int getx(int x) {
return lower_bound(all(vx), x) - vx.begin();
}
int gety(int y) {
return lower_bound(all(vy), y) - vy.begin();
}
struct rmq
{
vector<int> d, mod;
int ss = 1;
void init(int n) {
ss = 1;
while (ss < n) {
ss <<= 1;
}
d.resize(2 * ss);
mod.resize(2 * ss);
for (auto &x: d) {
x = -1;
}
for (auto &x: mod) {
x = -1;
}
}
void push(int v) {
if (mod[v] != -1) {
d[v] = mod[v];
if (v < ss) {
mod[v * 2] = mod[v];
mod[v * 2 + 1] = mod[v];
}
mod[v] = -1;
}
}
void add(int v, int vl, int vr, int l, int r, int x) {
if (vl > r || vr < l || l > r) {
return;
}
if (l <= vl && vr <= r) {
mod[v] = x;
return;
}
push(v);
add(v * 2, vl, (vl + vr) / 2, l, r, x);
add(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
}
int getval(int v, int vl, int vr, int i) {
push(v);
if (vl == vr) {
return d[v];
}
int mid = (vl + vr) / 2;
if (i <= mid) {
return getval(v * 2, vl, mid, i);
}
return getval(v * 2 + 1, mid + 1, vr, i);
}
};
rmq kek;
vector<int> z[MAXN * 2], z1[MAXN * 2];
vector<int> q[MAXN * 2], q1[MAXN * 2], zs[MAXN * 2], zs1[MAXN * 2];
int last[MAXN * 2], last1[MAXN * 2];
map<pair<int, int>, int> who;
vector<pair<int, int> > g[MAXN * 10];
int dist[MAXN * 10][5];
void add(int x, int y, int x1, int y1, int t) {
g[who[{x, y}]].pb({who[{x1, y1}], t});
// g[who[{x1, y1}]].pb({who[{x, y}], t ^ 1});
//cout << x << ' ' << y << ' ' << x1 << ' ' << y1 << endl;
}
int main() {
fast_io();
//read("input");
cin >> s >> t >> u >> v;
cin >> n;
vx.pb(s);
vx.pb(u);
vy.pb(t);
vy.pb(v);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
vx.pb(a[i]);
vx.pb(b[i]);
vy.pb(c[i]);
vy.pb(d[i]);
}
sort(all(vx));
vx.resize(distance(vx.begin(), unique(all(vx))));
sort(all(vy));
vy.resize(distance(vy.begin(), unique(all(vy))));
s = getx(s);
u = getx(u);
t = gety(t);
v = gety(v);
// cout << s << ' ' << t << ' ' << u << ' ' << v << endl;
for (int i = 0; i < n; i++) {
a[i] = getx(a[i]);
b[i] = getx(b[i]);
c[i] = gety(c[i]);
d[i] = gety(d[i]);
q[a[i]].pb(i);
z[b[i]].pb(i);
q1[c[i]].pb(i);
z1[d[i]].pb(i);
// cout << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << endl;
}
set<pair<int, int> > st;
for (int i = 0; i < n; i++) {
st.insert({a[i], c[i]});
st.insert({a[i], d[i]});
st.insert({b[i], c[i]});
st.insert({b[i], d[i]});
}
st.insert({s, t});
st.insert({u, v});
for (int i = 0; i < sz(vy); i++) {
st.insert({s, i});
st.insert({u, i});
}
for (int i = 0; i < sz(vx); i++) {
st.insert({i, t});
st.insert({i, v});
}
kek.init(sz(vy));
for (int i = 0; i < max(sz(vx), sz(vy)); i++) {
last[i] = -1;
last1[i] = -1;
}
for (int i = 0; i < sz(vx); i++) {
for (auto x: z[i]) {
//cout << i << endl;
kek.add(1, 1, kek.ss, c[x] + 1, d[x] + 1, i);
}
if (i == s) {
int f = kek.getval(1, 1, kek.ss, t + 1);
// cout << f << ' ' << t << endl;
st.insert({f, t});
}
if (i == u) {
int f = kek.getval(1, 1, kek.ss, t + 1);
st.insert({f, v});
}
for (auto y: q[i]) {
int f = kek.getval(1, 1, kek.ss, c[y] + 1);
st.insert({f, c[y]});
f = kek.getval(1, 1, kek.ss, d[y] + 1);
st.insert({f, d[y]});
}
}
kek.init(sz(vy));
for (int i = sz(vx) - 1; i >= 0; i--) {
for (auto x: q[i]) {
// cout << i << endl;
kek.add(1, 1, kek.ss, c[x] + 1, d[x] + 1, i);
}
if (i == s) {
int f = kek.getval(1, 1, kek.ss, t + 1);
// cout << f << ' ' << t << endl;
// cout << f << ' ' << t << endl;
st.insert({f, t});
}
if (i == u) {
int f = kek.getval(1, 1, kek.ss, v + 1);
st.insert({f, v});
}
for (auto y: z[i]) {
int f = kek.getval(1, 1, kek.ss, c[y] + 1);
st.insert({f, c[y]});
f = kek.getval(1, 1, kek.ss, d[y] + 1);
st.insert({f, d[y]});
}
}
kek.init(sz(vx));
for (int i = 0; i < sz(vy); i++) {
for (auto x: z1[i]) {
kek.add(1, 1, kek.ss, a[x] + 1, b[x] + 1, i);
}
if (i == t) {
int f = kek.getval(1, 1, kek.ss, s + 1);
st.insert({s, f});
}
if (i == v) {
int f = kek.getval(1, 1, kek.ss, u + 1);
st.insert({u, f});
}
for (auto y: q1[i]) {
int f = kek.getval(1, 1, kek.ss, a[y] + 1);
st.insert({a[y], f});
f = kek.getval(1, 1, kek.ss, b[y] + 1);
st.insert({b[y], f});
}
}
kek.init(sz(vx));
for (int i = sz(vy) - 1; i >= 0; i--) {
for (auto x: q1[i]) {
kek.add(1, 1, kek.ss, a[x] + 1, b[x] + 1, i);
}
if (i == t) {
int f = kek.getval(1, 1, kek.ss, s + 1);
st.insert({s, f});
}
if (i == v) {
int f = kek.getval(1, 1, kek.ss, u + 1);
st.insert({u, f});
}
for (auto y: z1[i]) {
int f = kek.getval(1, 1, kek.ss, a[y] + 1);
st.insert({a[y], f});
f = kek.getval(1, 1, kek.ss, b[y] + 1);
st.insert({b[y], f});
}
}
vector<pair<int, int> > st1;
for (auto x: st) {
if (x.first < 0 || x.second < 0) {
continue;
}
st1.pb(x);
}
int it = 0;
for (auto x: st1) {
who[x] = it;
//cout << x.first << ' ' << x.second << endl;
it++;
zs[x.first].pb(x.second);
zs1[x.second].pb(x.first);
}
kek.init(sz(vy));
for (int i = 0; i < sz(vx); i++) {
for (auto x: z[i]) {
//cout << i << endl;
kek.add(1, 1, kek.ss, c[x] + 2, d[x], i);
}
for (auto y: zs[i]) {
if (last[y] != -1) {
int ft = kek.getval(1, 1, kek.ss, y + 1);
// cout << last[y] << ' ' << y << ' ' << i << ' ' << y << endl;
if (ft == -1 || ft <= last[y]) {
add(last[y], y, i, y, 0);
}
}
last[y] = i;
}
}
kek.init(sz(vx));
for (int i = 0; i < sz(vy); i++) {
for (auto x: z1[i]) {
kek.add(1, 1, kek.ss, a[x] + 2, b[x], i);
}
for (auto y: zs1[i]) {
if (last1[y] != -1) {
//cout << y << ' ' << last1[y] << ' ' << y << ' ' << i << endl;
int ft = kek.getval(1, 1, kek.ss, y + 1);
//cout << ft << endl;
if (ft == -1 || ft <= last1[y]) {
add(y, last1[y], y, i, 2);
}
}
last1[y] = i;
}
}
for (int i = 0; i < max(sz(vx), sz(vy)); i++) {
last[i] = -1;
last1[i] = -1;
}
kek.init(sz(vy));
for (int i = sz(vx) - 1; i >= 0; i--) {
for (auto x: q[i]) {
kek.add(1, 1, kek.ss, c[x] + 2, d[x], i);
}
for (auto y: zs[i]) {
if (last[y] != -1) {
int ft = kek.getval(1, 1, kek.ss, y + 1);
if (ft == -1 || ft >= last[y]) {
add(last[y], y, i, y, 1);
}
}
last[y] = i;
}
}
kek.init(sz(vx));
for (int i = sz(vy) - 1; i >= 0; i--) {
for (auto x: q1[i]) {
kek.add(1, 1, kek.ss, a[x] + 2, b[x], i);
}
for (auto y: zs1[i]) {
if (last1[y] != -1) {
int ft = kek.getval(1, 1, kek.ss, y + 1);
if (ft == -1 || ft >= last1[y]) {
add(y, last1[y], y, i, 3);
}
}
last1[y] = i;
}
}
int m = sz(st1);
int start = who[{s, t}];
int finish = who[{u, v}];
for (int i = 0; i < m; i++) {
for (int t = 0; t < 4; t++) {
dist[i][t] = 1e9;
}
}
set<pair<int, pair<int, int> > > ft;
ft.insert({0, {start, 4}});
while (!ft.empty()) {
auto x = *ft.begin();
ft.erase(x);
int u = x.second.first;
int id = x.second.second;
for (auto h: g[u]) {
int de = h.first;
int kt = (h.second != id) + dist[u][id];
if (dist[de][h.second] > kt) {
ft.erase({dist[de][h.second], {de, h.second}});
dist[de][h.second] = kt;
ft.insert({dist[de][h.second], {de, h.second}});
}
}
}
int res = 1e9;
for (int t = 0; t < 4; t++) {
chkmin(res, dist[finish][t]);
}
cout << res << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
52096 KB |
Output is correct |
| 2 |
Correct |
35 ms |
52128 KB |
Output is correct |
| 3 |
Correct |
36 ms |
52224 KB |
Output is correct |
| 4 |
Correct |
46 ms |
52600 KB |
Output is correct |
| 5 |
Incorrect |
89 ms |
55392 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
52096 KB |
Output is correct |
| 2 |
Correct |
35 ms |
52128 KB |
Output is correct |
| 3 |
Correct |
36 ms |
52224 KB |
Output is correct |
| 4 |
Correct |
46 ms |
52600 KB |
Output is correct |
| 5 |
Incorrect |
89 ms |
55392 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
52096 KB |
Output is correct |
| 2 |
Correct |
35 ms |
52128 KB |
Output is correct |
| 3 |
Correct |
36 ms |
52224 KB |
Output is correct |
| 4 |
Correct |
46 ms |
52600 KB |
Output is correct |
| 5 |
Incorrect |
89 ms |
55392 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
