| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 398224 |
2021-05-04T01:05:04 Z |
duality |
Golf (JOI17_golf) |
C++11 |
|
1125 ms |
1048580 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; };
vector<seg> hor,ver;
struct seg2 { int z,l,r,t; };
bool comp(seg2 a,seg2 b) {
if (a.z == b.z) return a.t < b.t;
else return a.z < b.z;
}
vector<seg2> events;
set<pii> SS;
vi vv;
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[40000000];
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) {
int i,c = 0,d = 0;
for (i = 0; i < v.size(); i++) c += v[i].first == 0;
if (c == 0) {
v.clear();
return 0;
}
for (i = 0; i < v.size(); i++) {
if (v[i].first == 1) pos[v[i].second] = d;
else if (v[i].first == -1) update2(0,c-1,pos[v[i].second],d-1,0,v[i].second);
else d++;
}
d = 0;
build(0,c-1,0);
for (i = 0; i < v.size(); i++) {
if (v[i].first == 0) add2(0,c-1,d++,0,v[i].second);
}
clear(0,c-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[40000000];
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((seg2){C[i],A[i],B[i],1});
events.pb((seg2){D[i],A[i],B[i],-1});
}
events.pb((seg2){T,S,S,0});
events.pb((seg2){V,U,U,0});
sort(events.begin(),events.end(),comp);
SS.insert(mp(2e9,2e9));
SS.insert(mp(-2e9,-2e9));
for (i = 0; i < events.size(); i++) {
if (events[i].t == -1) SS.erase(mp(events[i].l,events[i].r));
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].t == 1) SS.insert(mp(events[i].l,events[i].r));
}
events.clear();
for (i = 0; i < N; i++) {
events.pb((seg2){A[i],C[i],D[i],1});
events.pb((seg2){B[i],C[i],D[i],-1});
}
events.pb((seg2){S,T,T,0});
events.pb((seg2){U,V,V,0});
sort(events.begin(),events.end(),comp);
for (i = 0; i < events.size(); i++) {
if (events[i].t == -1) SS.erase(mp(events[i].l,events[i].r));
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].t == 1) 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:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (j = 0; j < tree2[i].size(); j++) adjList[node[i]].pb(tree2[i][j]),adjList[tree2[i][j]].pb(node2[i]);
| ~~^~~~~~~~~~~~~~~~~
golf.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | 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:154: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]
154 | for (i = 0; i < v.size(); i++) c += v[i].first == 0;
| ~~^~~~~~~~~~
golf.cpp:159: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]
159 | for (i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
golf.cpp:166: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]
166 | for (i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:200:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
golf.cpp:216:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | for (i = 0; i < events.size(); i++) {
| ~~^~~~~~~~~~~~~~~
golf.cpp:227:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
227 | 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:228:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for (i = 0; i < ver.size(); i++) events2.pb(mp(ver[i].z,-(i+1)));
| ~~^~~~~~~~~~~~
golf.cpp:230: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]
230 | for (i = 0; i < events2.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
golf.cpp:252:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
252 | for (i = 0; i < ver.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:255:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for (i = 0; i < hor.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:262:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
262 | for (i = 0; i < adjList[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
golf.cpp:268:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
268 | for (i = 0; i < ver.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:271:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
271 | for (i = 0; i < hor.size(); i++) {
| ~~^~~~~~~~~~~~
golf.cpp:188:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
188 | scanf("%d %d %d %d %d",&S,&T,&U,&V,&N);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:189:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
189 | 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 |
600 ms |
988844 KB |
Output is correct |
| 2 |
Correct |
559 ms |
988868 KB |
Output is correct |
| 3 |
Correct |
560 ms |
988868 KB |
Output is correct |
| 4 |
Correct |
560 ms |
989172 KB |
Output is correct |
| 5 |
Correct |
567 ms |
990276 KB |
Output is correct |
| 6 |
Correct |
567 ms |
990260 KB |
Output is correct |
| 7 |
Correct |
572 ms |
990320 KB |
Output is correct |
| 8 |
Correct |
560 ms |
990276 KB |
Output is correct |
| 9 |
Correct |
583 ms |
990364 KB |
Output is correct |
| 10 |
Correct |
577 ms |
990252 KB |
Output is correct |
| 11 |
Correct |
561 ms |
990404 KB |
Output is correct |
| 12 |
Correct |
570 ms |
990404 KB |
Output is correct |
| 13 |
Correct |
570 ms |
990312 KB |
Output is correct |
| 14 |
Correct |
562 ms |
990276 KB |
Output is correct |
| 15 |
Correct |
569 ms |
989464 KB |
Output is correct |
| 16 |
Correct |
570 ms |
989892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
600 ms |
988844 KB |
Output is correct |
| 2 |
Correct |
559 ms |
988868 KB |
Output is correct |
| 3 |
Correct |
560 ms |
988868 KB |
Output is correct |
| 4 |
Correct |
560 ms |
989172 KB |
Output is correct |
| 5 |
Correct |
567 ms |
990276 KB |
Output is correct |
| 6 |
Correct |
567 ms |
990260 KB |
Output is correct |
| 7 |
Correct |
572 ms |
990320 KB |
Output is correct |
| 8 |
Correct |
560 ms |
990276 KB |
Output is correct |
| 9 |
Correct |
583 ms |
990364 KB |
Output is correct |
| 10 |
Correct |
577 ms |
990252 KB |
Output is correct |
| 11 |
Correct |
561 ms |
990404 KB |
Output is correct |
| 12 |
Correct |
570 ms |
990404 KB |
Output is correct |
| 13 |
Correct |
570 ms |
990312 KB |
Output is correct |
| 14 |
Correct |
562 ms |
990276 KB |
Output is correct |
| 15 |
Correct |
569 ms |
989464 KB |
Output is correct |
| 16 |
Correct |
570 ms |
989892 KB |
Output is correct |
| 17 |
Correct |
577 ms |
990440 KB |
Output is correct |
| 18 |
Correct |
560 ms |
990424 KB |
Output is correct |
| 19 |
Correct |
565 ms |
990480 KB |
Output is correct |
| 20 |
Correct |
572 ms |
990464 KB |
Output is correct |
| 21 |
Correct |
592 ms |
990396 KB |
Output is correct |
| 22 |
Correct |
566 ms |
990512 KB |
Output is correct |
| 23 |
Correct |
575 ms |
990472 KB |
Output is correct |
| 24 |
Correct |
576 ms |
990612 KB |
Output is correct |
| 25 |
Correct |
566 ms |
990404 KB |
Output is correct |
| 26 |
Correct |
576 ms |
990532 KB |
Output is correct |
| 27 |
Correct |
562 ms |
989408 KB |
Output is correct |
| 28 |
Correct |
567 ms |
990048 KB |
Output is correct |
| 29 |
Correct |
562 ms |
990060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
600 ms |
988844 KB |
Output is correct |
| 2 |
Correct |
559 ms |
988868 KB |
Output is correct |
| 3 |
Correct |
560 ms |
988868 KB |
Output is correct |
| 4 |
Correct |
560 ms |
989172 KB |
Output is correct |
| 5 |
Correct |
567 ms |
990276 KB |
Output is correct |
| 6 |
Correct |
567 ms |
990260 KB |
Output is correct |
| 7 |
Correct |
572 ms |
990320 KB |
Output is correct |
| 8 |
Correct |
560 ms |
990276 KB |
Output is correct |
| 9 |
Correct |
583 ms |
990364 KB |
Output is correct |
| 10 |
Correct |
577 ms |
990252 KB |
Output is correct |
| 11 |
Correct |
561 ms |
990404 KB |
Output is correct |
| 12 |
Correct |
570 ms |
990404 KB |
Output is correct |
| 13 |
Correct |
570 ms |
990312 KB |
Output is correct |
| 14 |
Correct |
562 ms |
990276 KB |
Output is correct |
| 15 |
Correct |
569 ms |
989464 KB |
Output is correct |
| 16 |
Correct |
570 ms |
989892 KB |
Output is correct |
| 17 |
Correct |
577 ms |
990440 KB |
Output is correct |
| 18 |
Correct |
560 ms |
990424 KB |
Output is correct |
| 19 |
Correct |
565 ms |
990480 KB |
Output is correct |
| 20 |
Correct |
572 ms |
990464 KB |
Output is correct |
| 21 |
Correct |
592 ms |
990396 KB |
Output is correct |
| 22 |
Correct |
566 ms |
990512 KB |
Output is correct |
| 23 |
Correct |
575 ms |
990472 KB |
Output is correct |
| 24 |
Correct |
576 ms |
990612 KB |
Output is correct |
| 25 |
Correct |
566 ms |
990404 KB |
Output is correct |
| 26 |
Correct |
576 ms |
990532 KB |
Output is correct |
| 27 |
Correct |
562 ms |
989408 KB |
Output is correct |
| 28 |
Correct |
567 ms |
990048 KB |
Output is correct |
| 29 |
Correct |
562 ms |
990060 KB |
Output is correct |
| 30 |
Runtime error |
1125 ms |
1048580 KB |
Execution killed with signal 9 |
| 31 |
Halted |
0 ms |
0 KB |
- |
