제출 #434339

#제출 시각아이디문제언어결과실행 시간메모리
434339lakshith_Rectangles (IOI19_rect)C++14
15 / 100
5044 ms480720 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define int long long #define what_is(a) cerr << #a << " is " << a << endl #define checker(a) cerr << "checker reached " << a << endl #define cout cerr const int MAXN = 1e3+1; const int K = 25; //sparce table struct sparce{ int log[MAXN+1]; int st[MAXN][K + 1]; int N; void init(vector<int> array){ N = array.size(); log[1] = 0; for (int i = 2; i <= MAXN; i++) log[i] = log[i/2] + 1; for (int i = 0; i < N; i++) st[i][0] = array[i]; for (int j = 1; j <= K; j++) for (int i = 0; i + (1 << j) <= N; i++) st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]); } int getMax(int L,int R){ int j = log[R - L + 1]; return max(st[L][j], st[R - (1 << j) + 1][j]); } }; sparce rows[1000],cols[1000]; bool check(int r1,int c1,int r2,int c2,vector<vector<signed>>& a){ for(int i=r1;i<=r2;i++){ //what_is(i); int r = rows[i].getMax(c1,c2); //cout <<c1 << " " << c2 << endl; //what_is(r); if(r>=a[i][c1-1]||r>=a[i][c2+1])return false; } for(int j=c1;j<=c2;j++){ int r = cols[j].getMax(r1,r2); if(r>=a[r1-1][j]||r>=a[r2+1][j])return false; } return true; } long long count_rectangles(std::vector<std::vector<signed> > a) { int n = a.size(),m=a[0].size(); //what_is(n); vector<int> vec; //precompute sparce for(int i=0;i<n;i++){ vec.clear(); for(int j=0;j<m;j++) vec.push_back(a[i][j]); rows[i].init(vec); } for(int j=0;j<m;j++){ vec.clear(); for(int i=0;i<n;i++) vec.push_back(a[i][j]); cols[j].init(vec); } int ans = 0; for(int r1=1;r1<n-1;r1++) for(int c1=1;c1<m-1;c1++) for(int r2=r1;r2<n-1;r2++) for(int c2=c1;c2<m-1;c2++){ //cout << r1 << " " << r2 << "\n"; ans += check(r1,c1,r2,c2,a); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...