Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2014
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.83 KB | None | 0 0
  1. #include<algorithm>
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<cstring>
  5. #include<cstdlib>
  6. #include<complex>
  7. #include<cstdio>
  8. #include<vector>
  9. #include<stack>
  10. #include<queue>
  11. #include<cmath>
  12. #include<deque>
  13. #include<map>
  14. #include<set>
  15. #define oo 1000000000
  16. #define ooll (1ll<<50)
  17. #define base 1000000007ll
  18. using namespace std;
  19. typedef long long ll;
  20. typedef pair<int,int> ii;
  21. typedef pair<int,ii> iii;
  22. typedef vector<int> vi;
  23. typedef vector<ii> vii;
  24. /* END OF TEMPLATE */
  25. //IOI 2014
  26. int R,C,n,m,ans,BIT[10000005];
  27. ii nans;
  28. vector<ii> row[1000005],col[1000005];
  29. vector<ii> qry[2][1000005];
  30. vector<int> open[2][1000005],close[2][1000005];
  31. void update(int x,int w) { for(; x<=C; x+=x&(-x)) BIT[x]+=w; }
  32. int query(int x)
  33. {
  34. int res=0;
  35. for(; x; x=x&(x-1)) res+=BIT[x];
  36. return res;
  37. }
  38. ii mn(ii u,ii v)
  39. {
  40. if(u.first==v.first) return u.second<v.second?u:v;
  41. return u.first<v.first?u:v;
  42. }
  43. void solve(int t)
  44. {
  45. bool fb=false;
  46. for(int i=1; i<=R; i++)
  47. {
  48. for(int j=0; j<open[t][i].size(); j++) update(open[t][i][j],1);
  49. sort(qry[!t][i].begin(),qry[!t][i].end());
  50. for(int j=0; j<qry[!t][i].size(); j++)
  51. {
  52. ii x=qry[!t][i][j];
  53. int d=query(x.second)-query(x.first-1);
  54. ans+=d;
  55. if(d && !fb)
  56. {
  57. fb=true;
  58. for(int k=x.first; k<=x.second; k++)
  59. if(query(k)!=query(k-1))
  60. {
  61. nans=mn(nans,ii(i,k));
  62. break;
  63. }
  64. }
  65. }
  66. for(int j=0; j<close[t][i].size(); j++) update(close[t][i][j],-1);
  67. }
  68. }
  69. bool dfs(int u,int v,int dir,int t)
  70. {
  71. int nu=u,nv=v,ndir;
  72. ii x;
  73. if(dir==0)
  74. {
  75. x=*(lower_bound(row[u].begin(),row[u].end(),ii(v,0))-1);
  76. nv=x.first;
  77. if(nv+1<v) qry[t][u].push_back(ii(nv+1,v-1));
  78. ndir=x.second?1:3;
  79. }
  80. if(dir==2)
  81. {
  82. x=*upper_bound(row[u].begin(),row[u].end(),ii(v,1));
  83. nv=x.first;
  84. if(v+1<nv) qry[t][u].push_back(ii(v+1,nv-1));
  85. ndir=x.second?3:1;
  86. }
  87. if(dir==1)
  88. {
  89. x=*(lower_bound(col[v].begin(),col[v].end(),ii(v,0))-1);
  90. nu=x.first;
  91. if(nu+1<u)
  92. {
  93. open[t][nu+1].push_back(v);
  94. close[t][u-1].push_back(v);
  95. }
  96. ndir=x.second?0:2;
  97. }
  98. if(dir==3)
  99. {
  100. x=*upper_bound(col[v].begin(),col[v].end(),ii(u,1));
  101. nu=x.first;
  102. if(u+1<nu)
  103. {
  104. open[t][u+1].push_back(v);
  105. close[t][nu-1].push_back(v);
  106. }
  107. ndir=x.second?2:0;
  108. }
  109. if(nu>=1 && nu<=R && nv>=1 && nv<=C) return dfs(nu,nv,ndir,t);
  110. return nu==R && nv==C+1;
  111. }
  112. int main()
  113. {
  114. freopen("laser.inp","r",stdin);
  115. freopen("laser.out","w",stdout);
  116. int u,v;
  117. scanf("%d %d %d %d",&R,&C,&n,&m);
  118. nans=ii(R,C);
  119. for(int i=1; i<=n; i++)
  120. {
  121. scanf("%d %d",&u,&v);
  122. row[u].push_back(ii(v,0));
  123. col[v].push_back(ii(u,0));
  124. }
  125. for(int i=1; i<=m; i++)
  126. {
  127. scanf("%d %d",&u,&v);
  128. row[u].push_back(ii(v,1));
  129. col[v].push_back(ii(u,1));
  130. }
  131. for(int i=1; i<=R; i++)
  132. {
  133. row[i].push_back(ii(0,0));
  134. row[i].push_back(ii(C+1,0));
  135. sort(row[i].begin(),row[i].end());
  136. }
  137. for(int i=1; i<=C; i++)
  138. {
  139. col[i].push_back(ii(0,0));
  140. col[i].push_back(ii(R+1,0));
  141. sort(col[i].begin(),col[i].end());
  142. }
  143. if(dfs(1,0,2,0))
  144. {
  145. printf("0\n");
  146. return 0;
  147. }
  148. dfs(R,C+1,0,1);
  149. solve(0);
  150. solve(1);
  151. if(ans==0) printf("Impossible\n");
  152. else printf("%d %d %d\n",ans,nans.first,nans.second);
  153. return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement