Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. #include <fstream>
  2.  
  3. #define NMAX 505
  4. using namespace std;
  5.  
  6. ifstream fin ( "or.in" );
  7. ofstream fout ( "or.out" );
  8.  
  9. int mat[NMAX][NMAX], L[NMAX], rmq[9][9][NMAX][NMAX];
  10.  
  11. int query(int stX, int stY, int fsX, int fsY){
  12. int powX = L[fsX - stX + 1];
  13. int powY = L[fsY - stY + 1];
  14. return (rmq[powX][powY][stX][stY] |
  15. rmq[powX][powY][stX][fsY - (1 << powY) + 1] |
  16. rmq[powX][powY][fsX - (1 << powX) + 1][stY] |
  17. rmq[powX][powY][fsX - (1 << powX) + 1][fsY - (1 << powY) + 1]);
  18. }
  19.  
  20. int main() {
  21. int x, n;
  22. fin >> x >> n;
  23.  
  24. for ( int i = 1; i <= n; ++i )
  25. for ( int j = 1; j <= n; ++j ){
  26. fin >> mat[i][j];
  27. rmq[0][0][i][j] = mat[i][j];
  28. }
  29.  
  30. for ( int i = 2; i <= n; ++i )
  31. L[i] = L[i / 2] + 1;
  32.  
  33. for(int p = 1; p <= L[n]; ++p)
  34. for(int i = 1; i <= n; ++i)
  35. for(int j = 1; j <= n; ++j)
  36. rmq[p][0][i][j] = (rmq[p - 1][0][i][j] | rmq[p - 1][0][i + (1 << (p - 1))][j]);
  37.  
  38. for ( int p = 0; p <= L[n]; ++p )
  39. for ( int q = 1; q <= L[n]; ++q )
  40. for ( int i = 1; i <= n; ++i )
  41. for ( int j = 1; j <= n; ++j )
  42. rmq[p][q][i][j] = (rmq[p][q - 1][i][j] | rmq[p][q - 1][i][j + ( 1 << ( q - 1 ) )]);
  43.  
  44. fout << query(3, 2, 4, 4);
  45. return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement