제출 #144277

#제출 시각아이디문제언어결과실행 시간메모리
144277shdutRectangles (IOI19_rect)C++14
0 / 100
10 ms10488 KiB
#include "rect.h" #include <vector> #include <map> #include <set> #include <algorithm> #include <iostream> using namespace std; #define inf 1000000007 #define SZ(x) x.size() #define N 2505 #define pb push_back #define x first #define y second #define ls p<<1 #define rs p<<1|1 #define vi std::vector<int> #define rep(i, a, b) for(int i = a; i < b; i++) #define DBG(x) cerr << (#x) << "=" << x << "\n"; int U[N][N], L[N][N], q[N], T[N], H[N], Q[N][N]; long long count_rectangles(std::vector<std::vector<int> > a) { //for(auto &o : a){ // for(auto &x : o)cerr << x << " "; // cerr << "\n"; //} int n = SZ(a), m = SZ(a[0]); rep(i, 0, n){ int t = 0; rep(j, 0, m){ while(t && a[i][q[t-1]] < a[i][j])t--; L[i][j] = t == 0 ? 0 : q[t-1]; //cerr << L[i][j] << " "; q[t++] = j; } //cerr << "\n"; } rep(j, 0, m){ int t = 0; rep(i, 0, n){ while(t && a[q[t-1]][j] < a[i][j])t--; U[i][j] = t == 0 ? 0 : q[t-1]; //cerr << U[i][j] << " "; q[t++] = i; } //cerr << "\n"; } rep(i, 0, m)H[i] = T[i] = 0; long long ans = 0; rep(i, 0, n){ int t = 0; rep(j, 0, m-1){ while(t && U[i][q[t-1]] <= U[i][j])t--; q[t++] = j; int k = j+1; //DBG(U[i][j]) //while(H[k] < T[k] && Q[k][H[k]] <= U[i][j]){ // H[k]++; //} if(i >=2 && j){ int x = t-1, y = 0, w = L[i-1][k]; while(y < T[k] && Q[k][y] <= U[i][j])y++; //cerr << i << " " << j << ":\n"; //cerr << q[x] << " " << Q[k][y] << " " << U[i][q[x]] << ", " << L[Q[k][y]][k] << "\n"; while(x >= 0 && q[x] > w){ while(y < T[j] && Q[k][y] <= U[i][q[x]])y++; while(y < T[j] && L[Q[k][y]][k] >= q[x])y++; if(y == T[k])break; int z = y == 0 ? 1 : Q[k][y-1] + 1; //cerr << z << " " << i << ", " << q[x] << " " << j << "\n"; ans += (j - q[x] + 1) * max(i - z, 0); x--; } } } rep(j, 0, m){ while(H[j] < T[j] && L[Q[j][T[j]-1]][j] <= L[i][j])T[j]--; Q[j][T[j]++] = i; } } 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...