| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 398215 |
2021-05-04T00:41:21 Z |
duality |
Golf (JOI17_golf) |
C++11 |
|
90 ms |
124032 KB |
#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
int A[100000],B[100000],C[100000],D[100000];
struct seg { int z,l,r; };
bool comp(seg a,seg b) {
return a.z < b.z;
}
vector<seg> events;
set<pii> SS;
vi vv;
vector<seg> hor,ver;
vpii events2;
vpii tree[1 << 20];
int update(int s,int e,int ai,int i,int t,int u) {
if ((s > ai) || (e < ai)) return 0;
else if (s == e) {
tree[i].pb(mp(t,u));
return 0;
}
int mid = (s+e) / 2;
update(s,mid,ai,2*i+1,t,u),update(mid+1,e,ai,2*i+2,t,u);
tree[i].pb(mp(t,u));
return 0;
}
int add(int s,int e,int as,int ae,int i,int u) {
if ((s > ae) || (e < as)) return 0;
else if ((s >= as) && (e <= ae)) {
tree[i].pb(mp(0,u));
return 0;
}
int mid = (s+e) / 2;
add(s,mid,as,ae,2*i+1,u),add(mid+1,e,as,ae,2*i+2,u);
return 0;
}
vi adjList[3000000];
int num;
int pos[600000];
vi tree2[1 << 20];
int node[1 << 20],node2[1 << 20];
int update2(int s,int e,int as,int ae,int i,int u) {
if ((s > ae) || (e < as)) return 0;
else if ((s >= as) && (e <= ae)) {
tree2[i].pb(u);
return 0;
}
int mid = (s+e) / 2;
update2(s,mid,as,ae,2*i+1,u),update2(mid+1,e,as,ae,2*i+2,u);
return 0;
}
int build(int s,int e,int i) {
if (s == e) {
if (!tree2[i].empty()) {
int j;
node[i] = num++,node2[i] = num++;
for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
}
return 0;
}
int mid = (s+e) / 2;
build(s,mid,2*i+1),build(mid+1,e,2*i+2);
if (!tree2[i].empty()) {
int j;
node[i] = num++,node2[i] = num++;
for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
}
return 0;
}
int add2(int s,int e,int ai,int i,int u) {
if ((s > ai) || (e < ai)) return 0;
else if (s == e) {
if (!tree2[i].empty()) adjList[u].pb(node[i]),adjList[node2[i]].pb(u);
return 0;
}
int mid = (s+e) / 2;
add2(s,mid,ai,2*i+1,u),add2(mid+1,e,ai,2*i+2,u);
if (!tree2[i].empty()) adjList[u].pb(node[i]),adjList[node2[i]].pb(u);
return 0;
}
int clear(int s,int e,int i) {
if (s == e) {
tree2[i].clear();
return 0;
}
int mid = (s+e) / 2;
clear(s,mid,2*i+1),clear(mid+1,e,2*i+2);
tree2[i].clear();
return 0;
}
int process(vpii &v) {
if (v.empty()) return 0;
int i;
for (i = 0; i < v.size(); i++) {
if (v[i].first == 1) pos[v[i].second] = i;
else if (v[i].first == -1) update2(0,v.size()-1,pos[v[i].second],i,0,v[i].second);
}
build(0,v.size()-1,0);
for (i = 0; i < v.size(); i++) {
if (v[i].first == 0) add2(0,v.size()-1,i,0,v[i].second);
}
clear(0,v.size()-1,0),v.clear();
return 0;
}
int process(int s,int e,int i) {
if (s == e) {
process(tree[i]);
return 0;
}
int mid = (s+e) / 2;
process(s,mid,2*i+1),process(mid+1,e,2*i+2);
process(tree[i]);
return 0;
}
int dist[3000000];
queue<int> Q;
int main() {
int i;
int N,S,T,U,V;
scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
for (i = 0; i < N; i++) scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
for (i = 0; i < N; i++) {
events.pb((seg){C[i],A[i],B[i]});
events.pb((seg){D[i],A[i],B[i]});
}
events.pb((seg){T,S,S});
events.pb((seg){V,U,U});
sort(events.begin(),events.end(),comp);
SS.insert(mp(2e9,2e9));
SS.insert(mp(-2e9,-2e9));
for (i = 0; i < events.size(); i++) {
int e = 0;
if ((events[i].l != events[i].r) && SS.count(mp(events[i].l,events[i].r))) SS.erase(mp(events[i].l,events[i].r)),e = 1;
auto it = SS.lower_bound(mp(events[i].l,0));
auto it2 = it;
it--;
hor.pb((seg){events[i].z,it->second,it2->first}),vv.pb(events[i].z);
if ((events[i].l != events[i].r) && !e) SS.insert(mp(events[i].l,events[i].r));
}
events.clear();
for (i = 0; i < N; i++) {
events.pb((seg){A[i],C[i],D[i]});
events.pb((seg){B[i],C[i],D[i]});
}
events.pb((seg){S,T,T});
events.pb((seg){U,V,V});
sort(events.begin(),events.end(),comp);
for (i = 0; i < events.size(); i++) {
int e = 0;
if ((events[i].l != events[i].r) && SS.count(mp(events[i].l,events[i].r))) SS.erase(mp(events[i].l,events[i].r)),e = 1;
auto it = SS.lower_bound(mp(events[i].l,0));
auto it2 = it;
it--;
ver.pb((seg){events[i].z,it->second,it2->first});
if ((events[i].l != events[i].r) && !e) SS.insert(mp(events[i].l,events[i].r));
}
sort(vv.begin(),vv.end());
vv.resize(unique(vv.begin(),vv.end())-vv.begin());
for (i = 0; i < hor.size(); i++) events2.pb(mp(hor[i].l,-(i+ver.size()+1))),events2.pb(mp(hor[i].r,i+ver.size()+1));
for (i = 0; i < ver.size(); i++) events2.pb(mp(ver[i].z,-(i+1)));
sort(events2.begin(),events2.end());
for (i = 0; i < events2.size(); i++) {
if (events2[i].second < -(int) ver.size()) {
int u = -events2[i].second-1;
int p = lower_bound(vv.begin(),vv.end(),hor[u-ver.size()].z)-vv.begin();
update(0,vv.size()-1,p,0,1,u);
}
else if (events2[i].second < 0) {
int u = -events2[i].second-1;
int p = lower_bound(vv.begin(),vv.end(),ver[u].l)-vv.begin();
int q = upper_bound(vv.begin(),vv.end(),ver[u].r)-vv.begin()-1;
add(0,vv.size()-1,p,q,0,u);
}
else {
int u = events2[i].second-1;
int p = lower_bound(vv.begin(),vv.end(),hor[u-ver.size()].z)-vv.begin();
update(0,vv.size()-1,p,0,-1,u);
}
}
num = hor.size()+ver.size();
process(0,vv.size()-1,0);
for (i = 0; i < num; i++) dist[i] = -1;
for (i = 0; i < ver.size(); i++) {
if ((ver[i].z == S) && (ver[i].l <= T) && (ver[i].r >= T)) dist[i] = 0,Q.push(i);
}
for (i = 0; i < hor.size(); i++) {
if ((hor[i].z == T) && (hor[i].l <= S) && (hor[i].r >= S)) dist[i+ver.size()] = 0,Q.push(i+ver.size());
}
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (i = 0; i < adjList[u].size(); i++) {
int v = adjList[u][i];
if (dist[v] == -1) dist[v] = dist[u]+1,Q.push(v);
}
}
int ans = 1e9;
for (i = 0; i < ver.size(); i++) {
if ((ver[i].z == U) && (ver[i].l <= V) && (ver[i].r >= V)) ans = min(ans,dist[i]);
}
for (i = 0; i < hor.size(); i++) {
if ((hor[i].z == V) && (hor[i].l <= U) && (hor[i].r >= U)) ans = min(ans,dist[i+ver.size()]);
}
printf("%d\n",ans/2+1);
return 0;
}
Compilation message
golf.cpp: In function 'int build(int, int, int)':
golf.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
| ~~^~~~~~~~~~~~~~~~~
golf.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
| ~~^~~~~~~~~~~~~~~~~
golf.cpp: In function 'int process(vpii&)':
golf.cpp:153:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
golf.cpp:158:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for (i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:192:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
golf.cpp:209:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
209 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
golf.cpp:220:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | for (i = 0; i < hor.size(); i++) events2.pb(mp(hor[i].l,-(i+ver.size()+1))),events2.pb(mp(hor[i].r,i+ver.size()+1));
| ~~^~~~~~~~~~~~
golf.cpp:221:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | for (i = 0; i < ver.size(); i++) events2.pb(mp(ver[i].z,-(i+1)));
| ~~^~~~~~~~~~~~
golf.cpp:223:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for (i = 0; i < events2.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
golf.cpp:244:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
244 | for (i = 0; i < ver.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:247:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for (i = 0; i < hor.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:254:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
254 | for (i = 0; i < adjList[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
golf.cpp:260:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
260 | for (i = 0; i < ver.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:263:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
263 | for (i = 0; i < hor.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
180 | scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:181:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
181 | for (i = 0; i < N; i++) scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
120036 KB |
Output is correct |
| 2 |
Correct |
61 ms |
120032 KB |
Output is correct |
| 3 |
Correct |
62 ms |
120044 KB |
Output is correct |
| 4 |
Correct |
63 ms |
120324 KB |
Output is correct |
| 5 |
Correct |
86 ms |
123924 KB |
Output is correct |
| 6 |
Correct |
90 ms |
123896 KB |
Output is correct |
| 7 |
Correct |
87 ms |
124032 KB |
Output is correct |
| 8 |
Incorrect |
87 ms |
123908 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
120036 KB |
Output is correct |
| 2 |
Correct |
61 ms |
120032 KB |
Output is correct |
| 3 |
Correct |
62 ms |
120044 KB |
Output is correct |
| 4 |
Correct |
63 ms |
120324 KB |
Output is correct |
| 5 |
Correct |
86 ms |
123924 KB |
Output is correct |
| 6 |
Correct |
90 ms |
123896 KB |
Output is correct |
| 7 |
Correct |
87 ms |
124032 KB |
Output is correct |
| 8 |
Incorrect |
87 ms |
123908 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
120036 KB |
Output is correct |
| 2 |
Correct |
61 ms |
120032 KB |
Output is correct |
| 3 |
Correct |
62 ms |
120044 KB |
Output is correct |
| 4 |
Correct |
63 ms |
120324 KB |
Output is correct |
| 5 |
Correct |
86 ms |
123924 KB |
Output is correct |
| 6 |
Correct |
90 ms |
123896 KB |
Output is correct |
| 7 |
Correct |
87 ms |
124032 KB |
Output is correct |
| 8 |
Incorrect |
87 ms |
123908 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
