Submission #398226

#TimeUsernameProblemLanguageResultExecution timeMemory
398226dualityGolf (JOI17_golf)C++11
100 / 100
2731 ms340936 KiB
#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 << 19]; 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[5000000]; int num; int pos[400004]; vi tree2[1 << 19]; int node[1 << 19],node2[1 << 19]; 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[5000000]; 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...