| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122480 |
2019-06-28T11:32:41 Z |
egorlifar |
Golf (JOI17_golf) |
C++17 |
|
0 ms |
0 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);
}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
struct rect {
rect(){}
rect(int x1, int x2, int y1, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}
int x1, x2, y1, y2;
};
struct seg {
seg(){}
seg(int x1, int x2, int y, int c) : x1(x1), x2(x2), y(y), c(c) {}
int x1, x2, y, c;
bool operator<(const seg &rhs)const {
if(y != rhs.y) return y < rhs.y;
return c < rhs.c;
}
};
pii LR[400040];
vector <seg> V;
vector <int> vx, vy;
rect P[100010];
int N, cs, LX;
int T[1<<19];
void update_t2(int rt, int l, int r, int s, int e, int val) {
if(s <= l && r <= e) {
T[rt] = val; return;
}
if(T[rt]) {
T[rt<<1] = T[rt];
T[rt<<1|1] = T[rt];
T[rt] = 0;
}
int m = (l + r) >> 1;
if(s <= m) update_t2(rt<<1, l, m, s, e, val);
if(m < e) update_t2(rt<<1|1, m+1, r, s, e, val);
}
int read_t2(int rt, int l, int r, int x) {
if(l == r) return T[rt];
if(T[rt] != 0) return T[rt];
int m = (l + r) >> 1;
if(x <= m) return read_t2(rt<<1, l, m, x);
else return read_t2(rt<<1|1, m+1, r, x);
}
void update_t(int l, int r, int val) {
if(l <= r) update_t2(1, 0, LX, l, r, val);
}
int read_t(int x) {
return read_t2(1, 0, LX, x);
}
void flip_xy() {
swap(vx, vy); for(int i=1;i<=N;i++) swap(P[i].x1, P[i].y1), swap(P[i].x2, P[i].y2);
}
void get_line(int cmd) {
for(int i=1;i<=N;i++) {
V.pb(seg(P[i].x1+1, P[i].x2-1, P[i].y2, 1));
V.pb(seg(P[i].x1, 4*i+cmd, P[i].y1, -1));
V.pb(seg(P[i].x2, 4*i+1+cmd, P[i].y1, -1));
}
sort(all(V));
for(auto &s : V) {
if(s.c < 0) {
LR[s.x2].Fi = read_t(s.x1);
}
else {
update_t(s.x1, s.x2, s.y);
}
}
memset(T, 0, sizeof T); V.clear();
for(int i=1;i<=N;i++) {
V.pb(seg(P[i].x1+1, P[i].x2-1, -P[i].y1, 1));
V.pb(seg(P[i].x1, 4*i+cmd, -P[i].y2, -1));
V.pb(seg(P[i].x2, 4*i+1+cmd, -P[i].y2, -1));
}
sort(all(V));
for(auto &s : V) {
if(s.c < 0) {
int v = -read_t(s.x1);
if(v == 0) v = LX;
LR[s.x2].Se = v;
}
else {
update_t(s.x1, s.x2, s.y);
}
}
memset(T, 0, sizeof T); V.clear();
}
int dis[400040];
set <pii> Sx[2][1<<19]; const int ADD = 1<<18;
void update(int a, int x, int y1, int y2, int val) {
y1 += ADD; y2 += ADD;
while(y1 <= y2) {
if(y1 & 1) Sx[a][y1++].insert(pii(x, val));
if(!(y2 & 1)) Sx[a][y2--].insert(pii(x, val));
y1 >>= 1, y2 >>= 1;
}
}
int read(int a, int x1, int x2, int y) {
y += ADD;
while(y) {
auto it = Sx[a][y].lower_bound(pii(x1, -1));
while(1) {
if(it == Sx[a][y].end() || it->Fi > x2) break;
if(dis[it->Se] == -1) return it->Se;
auto jt = it++;
Sx[a][y].erase(jt);
}
y >>= 1;
}
return -1;
}
int pp[400040]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int main() {
int ss, tt, uu, vv; scanf("%d%d%d%d", &ss, &tt, &uu, &vv);
scanf("%d", &N);
P[1] = rect(ss, ss, tt, tt);
P[2] = rect(uu, uu, vv, vv);
for(int i=3;i<=N+2;i++) {
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
P[i] = rect(x1, x2, y1, y2);
}
N += 2;
for(int i=1;i<=N;i++) {
vx.pb(P[i].x1); vx.pb(P[i].x2);
vy.pb(P[i].y1); vy.pb(P[i].y2);
}
sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
for(int i=1;i<=N;i++) {
P[i].x1 = (int)(lower_bound(all(vx), P[i].x1) - vx.begin() + 1);
P[i].x2 = (int)(lower_bound(all(vx), P[i].x2) - vx.begin() + 1);
P[i].y1 = (int)(lower_bound(all(vy), P[i].y1) - vy.begin() + 1);
P[i].y2 = (int)(lower_bound(all(vy), P[i].y2) - vy.begin() + 1);
}
LX = max(szz(vx), szz(vy)) + 1;
get_line(0);
flip_xy();
get_line(2);
flip_xy();
map <t3, int> Mx[2];
rep(i, 4*N+5) pp[i] = i;
for(int i=1;i<=N;i++) {
rep(a, 4) {
pii p = LR[4*i+a];
t3 t;
if(a == 0) t = t3(P[i].x1, p.Fi, p.Se);
else if(a == 1) t = t3(P[i].x2, p.Fi, p.Se);
else if(a == 2) t = t3(P[i].y1, p.Fi, p.Se);
else t = t3(P[i].y2, p.Fi, p.Se);
int ta = !!(a & 2);
if(Mx[ta].find(t) == Mx[ta].end()) Mx[ta][t] = 4*i+a;
else pp[Find(4*i+a)] = Find(Mx[ta][t]);
}
}
for(int i=4;i<4*N+4;i++) if(pp[i] == i) {
if(i&2) {
int x = (i%4==2 ? P[i/4].y1 : P[i/4].y2);
update(1, x, LR[i].Fi, LR[i].Se, i);
}
else {
int x = (i%4==0 ? P[i/4].x1 : P[i/4].x2);
update(0, x, LR[i].Fi, LR[i].Se, i);
}
}
memset(dis, -1, sizeof dis);
vector <int> q;
for(int i=4;i<=7;i++) {
int pi = Find(i);
if(dis[pi] == -1) {
dis[pi] = 1; q.pb(pi);
}
}
for(int i=8;i<12;i++) if(dis[Find(i)] == 1) {
puts("1");
return 0;
}
rep(i, szz(q)) {
int t = q[i];
while(1) {
int v = -1;
if(t&2) {
int x = (t%4==2 ? P[t/4].y1 : P[t/4].y2);
v = read(0, LR[t].Fi, LR[t].Se, x);
}
else {
int x = (t%4==0 ? P[t/4].x1 : P[t/4].x2);
v = read(1, LR[t].Fi, LR[t].Se, x);
}
if(v == -1) break;
q.pb(v); dis[v] = dis[t] + 1;
for(int i=8;i<12;i++) if(Find(i) == v) {
printf("%d\n", dis[v]);
return 0;
}
}
}
int ans = 1e9;
for(int i=8;i<12;i++) {
int pi = Find(i);
if(dis[pi] != -1) ans = min(ans, dis[pi]);
}
printf("%d\n", ans);
return 0;
}
Compilation message
golf.cpp:100:0: warning: "pb" redefined
#define pb(x) push_back(x)
golf.cpp:73:0: note: this is the location of the previous definition
#define pb push_back
golf.cpp:103:0: warning: "all" redefined
#define all(x) x.begin(),x.end()
golf.cpp:70:0: note: this is the location of the previous definition
#define all(c) (c).begin(), (c).end()
golf.cpp:208:38: error: macro "read" passed 4 arguments, but takes just 1
int read(int a, int x1, int x2, int y) {
^
golf.cpp:300:38: error: macro "read" passed 4 arguments, but takes just 1
v = read(0, LR[t].Fi, LR[t].Se, x);
^
golf.cpp:304:38: error: macro "read" passed 4 arguments, but takes just 1
v = read(1, LR[t].Fi, LR[t].Se, x);
^
golf.cpp: In constructor 'rect::rect(int, int, int, int)':
golf.cpp:109:14: warning: 'rect::y1' will be initialized after [-Wreorder]
int x1, x2, y1, y2;
^~
golf.cpp:109:10: warning: 'int rect::x2' [-Wreorder]
int x1, x2, y1, y2;
^~
golf.cpp:108:2: warning: when initialized here [-Wreorder]
rect(int x1, int x2, int y1, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}
^~~~
golf.cpp: At global scope:
golf.cpp:209:2: error: 'y' was not declared in this scope
y += ADD;
^
golf.cpp:209:10: error: expected '}' before ';' token
y += ADD;
^
golf.cpp:210:2: error: expected unqualified-id before 'while'
while(y) {
^~~~~
golf.cpp:220:2: error: expected unqualified-id before 'return'
return -1;
^~~~~~
golf.cpp:221:1: error: expected declaration before '}' token
}
^
