Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #define NMAX 505
- using namespace std;
- ifstream fin ( "or.in" );
- ofstream fout ( "or.out" );
- int mat[NMAX][NMAX], L[NMAX], rmq[9][9][NMAX][NMAX];
- int query(int stX, int stY, int fsX, int fsY){
- int powX = L[fsX - stX + 1];
- int powY = L[fsY - stY + 1];
- return (rmq[powX][powY][stX][stY] |
- rmq[powX][powY][stX][fsY - (1 << powY) + 1] |
- rmq[powX][powY][fsX - (1 << powX) + 1][stY] |
- rmq[powX][powY][fsX - (1 << powX) + 1][fsY - (1 << powY) + 1]);
- }
- int main() {
- int x, n;
- fin >> x >> n;
- for ( int i = 1; i <= n; ++i )
- for ( int j = 1; j <= n; ++j ){
- fin >> mat[i][j];
- rmq[0][0][i][j] = mat[i][j];
- }
- for ( int i = 2; i <= n; ++i )
- L[i] = L[i / 2] + 1;
- for(int p = 1; p <= L[n]; ++p)
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= n; ++j)
- rmq[p][0][i][j] = (rmq[p - 1][0][i][j] | rmq[p - 1][0][i + (1 << (p - 1))][j]);
- for ( int p = 0; p <= L[n]; ++p )
- for ( int q = 1; q <= L[n]; ++q )
- for ( int i = 1; i <= n; ++i )
- for ( int j = 1; j <= n; ++j )
- rmq[p][q][i][j] = (rmq[p][q - 1][i][j] | rmq[p][q - 1][i][j + ( 1 << ( q - 1 ) )]);
- fout << query(3, 2, 4, 4);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement