| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 100914 |
2019-03-15T06:51:54 Z |
cki86201 |
Golf (JOI17_golf) |
C++11 |
|
85 ms |
59744 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>
using namespace std;
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) {
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];
struct node {
node(){link[0] = link[1] = 0;}
node* link[2];
vector <int> v;
void update(int l, int r, int s, int e, int x) {
if(s <= l && r <= e) {
v.pb(x);
return;
}
int m = (l + r) >> 1;
if(s <= m) {
if(!link[0]) link[0] = new node();
link[0]->update(l, m, s, e, x);
}
if(m < e) {
if(!link[1]) link[1] = new node();
link[1]->update(m+1, r, s, e, x);
}
}
int read(int l, int r, int x) {
while(szz(v)) {
int a = v.back(); v.pop_back();
if(dis[a] == -1) return a;
}
if(l == r) return -1;
int m = (l + r) >> 1;
if(x <= m) return link[0]?link[0]->read(l, m, x):-1;
else return link[1]?link[1]->read(m+1, r, x):-1;
}
};
node H[2][1<<19]; const int ADD = 1<<18;
void update(int a, int x, int y1, int y2, int idx) {
x += ADD;
while(x) H[a][x].update(0, LX, y1, y2, idx), x >>= 1;
}
int read(int a, int l, int r, int y) {
l += ADD, r += ADD;
while(l <= r) {
if(l & 1) {
int v = H[a][l++].read(0, LX, y);
if(v != -1) return v;
}
if(!(r & 1)) {
int v = H[a][r--].read(0, LX, y);
if(v != -1) return v;
}
l >>= 1, r >>= 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); vx.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();
/*
for(int i=1;i<=N;i++) {
for(int a=0;a<4;a++) {
printf("%d %d\n", LR[4*i+a].Fi, LR[4*i+a].Se);
}
}
*/
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);
}
}
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;
}
}
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: In constructor 'rect::rect(int, int, int, int)':
golf.cpp:35:14: warning: 'rect::y1' will be initialized after [-Wreorder]
int x1, x2, y1, y2;
^~
golf.cpp:35:10: warning: 'int rect::x2' [-Wreorder]
int x1, x2, y1, y2;
^~
golf.cpp:34: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: In function 'int main()':
golf.cpp:177:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int ss, tt, uu, vv; scanf("%d%d%d%d", &ss, &tt, &uu, &vv);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
golf.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
45048 KB |
Output is correct |
| 2 |
Correct |
32 ms |
45056 KB |
Output is correct |
| 3 |
Correct |
43 ms |
45032 KB |
Output is correct |
| 4 |
Correct |
38 ms |
46456 KB |
Output is correct |
| 5 |
Incorrect |
85 ms |
59744 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
45048 KB |
Output is correct |
| 2 |
Correct |
32 ms |
45056 KB |
Output is correct |
| 3 |
Correct |
43 ms |
45032 KB |
Output is correct |
| 4 |
Correct |
38 ms |
46456 KB |
Output is correct |
| 5 |
Incorrect |
85 ms |
59744 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
45048 KB |
Output is correct |
| 2 |
Correct |
32 ms |
45056 KB |
Output is correct |
| 3 |
Correct |
43 ms |
45032 KB |
Output is correct |
| 4 |
Correct |
38 ms |
46456 KB |
Output is correct |
| 5 |
Incorrect |
85 ms |
59744 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
