Submission #809216

#TimeUsernameProblemLanguageResultExecution timeMemory
809216Username4132Rectangles (IOI19_rect)C++14
27 / 100
496 ms1048576 KiB
#include "rect.h" #include<iostream> #include<vector> using namespace std; using ll = long long; using ull = unsigned long long; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) #define dforsn(i, s, n) for(int i=n-1; i>=s; --i) #define PB push_back const int MAXN = 710; ull mask[MAXN][MAXN], moved[MAXN]; // column, start row int n, m, arr[MAXN][MAXN], brr[MAXN][MAXN], maa[MAXN][MAXN]; int far[MAXN][MAXN][MAXN]; // row, l, r void calc1(){ dforn(row, n){ forsn(i, 1, m-1){ int mx = -1; forsn(j, i, m-1){ mx = max(mx, arr[row][j]); if(mx<arr[row][i-1] && mx<arr[row][j+1]){ far[row][i][j]=far[row+1][i][j]; } else far[row][i][j]=row; } } } } void calc2(int x){ forn(i, n) forn(j, m) mask[i][j]=0; forn(col, m){ forsn(i, 1, n-1){ forsn(j, i+(x<<6), min(n-1, i + ((x+1)<<6))){ maa[col][i] = max(maa[col][i], brr[col][j]); if(maa[col][i]<brr[col][i-1] && maa[col][i]<brr[col][j+1]){ mask[i][col]|=(1ull<<(j-i-(x<<6))); } } } } } long long count_rectangles(std::vector<std::vector<int> > a) { n=(int)a.size(), m=(int)a.front().size(); //forn(i, 800) full|=(one<<i); moved[0]=0; forn(i, 64) moved[i+1]=(moved[i]<<1)|1; forn(i, n) forn(j, m) brr[j][i]=arr[i][j]=a[i][j]; forn(i, m) forn(j, m) far[n][i][j]=n; calc1(); ll ans=0; forn(x, (n+63)>>6){ calc2(x); forsn(row, 1, n-1){ forsn(i, 1, m-1){ ull bt = ~0ull; forsn(j, i, m-1){ bt&=mask[row][j]; ans+=__builtin_popcountll((bt&moved[min(far[row][i][j]-row-(x<<6), 64)])); } } } } 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...