Submission #1047689

#TimeUsernameProblemLanguageResultExecution timeMemory
1047689fuad27Rectangles (IOI19_rect)C++17
72 / 100
5085 ms797780 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") const int N = 2510; int n,m; vector<array<int, 2>> gdr[N][N]; vector<array<int, 2>> gdc[N][N]; struct Side { int r1, r2, c1, c2; }; int fen[N]; void upd(int at, int add) { at++; while(at) { fen[at]+=add; at-=at&(-at); } } int qry(int at) { at++; int sum=0; while(at<N) { sum+=fen[at]; at+=at&(-at); } return sum; } vector<int> stk; long long count_rectangles(std::vector<std::vector<int> > a) { n = a.size(); m = a[0].size(); for(int i = 0;i<n;i++) { stk.clear(); for(int j = 0;j<m;j++) { while(stk.size() and a[i][stk.back()] < a[i][j]){ stk.pop_back(); } if(stk.size()) { gdr[i][j].push_back({stk.back(), 1}); } stk.push_back(j); } stk.clear(); for(int j = m-1;j>=0;j--) { while(stk.size() and a[i][stk.back()] < a[i][j])stk.pop_back(); if(stk.size()) { if(a[i][j] != a[i][stk.back()]) { gdr[i][stk.back()].push_back({j,1}); } } stk.push_back(j); } } for(int i = 0;i<m;i++) { stk.clear(); for(int j = 0;j<n;j++) { while(stk.size() and a[stk.back()][i] < a[j][i]){ stk.pop_back(); } if(stk.size()) { gdc[j][i].push_back({stk.back(),1}); } stk.push_back(j); } stk.clear(); for(int j = n-1;j>=0;j--) { while(stk.size() and a[stk.back()][i] < a[j][i])stk.pop_back(); if(stk.size()) { if(a[j][i] != a[stk.back()][i]) { gdc[stk.back()][i].push_back({j, 1}); } } stk.push_back(j); } } long long ans=0; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { sort(gdr[i][j].begin(), gdr[i][j].end()); sort(gdc[i][j].begin(), gdc[i][j].end()); gdr[i][j].erase(unique(gdr[i][j].begin(), gdr[i][j].end()), gdr[i][j].end()); gdc[i][j].erase(unique(gdc[i][j].begin(), gdc[i][j].end()), gdc[i][j].end()); if(i) { for(auto &[u, v]:gdr[i][j]) { auto it = lower_bound(gdr[i-1][j].begin(), gdr[i-1][j].end(), array<int,2>{u, 0}); if(it!=gdr[i-1][j].end() and (*it)[0] == u) { v+=(*it)[1]; } } } if(j) { for(auto &[u, v]:gdc[i][j]) { auto it = lower_bound(gdc[i][j-1].begin(), gdc[i][j-1].end(), array<int,2>{u, 0}); if(it!=gdc[i][j-1].end() and (*it)[0] == u) { v+=(*it)[1]; } } } if(i and j) { for(auto k:gdr[i-1][j]) { if(k[0] +1 == j)continue; for(auto k2:gdc[i][j-1]) { if(k2[0] +1 == i)continue; // cout << i << " " << j << " " << k[0] << " " << k2[0] << " " << k[1] << " " << k2[1] << endl; if(k[0] >= j - k2[1]-1 and k2[0] >= i - k[1] - 1)ans++; } } } } } 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...