Submission #212030

#TimeUsernameProblemLanguageResultExecution timeMemory
212030anonymousRectangles (IOI19_rect)C++14
0 / 100
192 ms295928 KiB
#include "rect.h" #include<set> #include<vector> #include<algorithm> #include<utility> #define MAXN 2505 using namespace std; int N,M,A[MAXN][MAXN]; vector<pair<int,int> > Hor[MAXN][MAXN], Vert[MAXN][MAXN]; set<pair<int,int> > HorM[MAXN], VertM[MAXN]; //unordered? vector<pair<int,int> > S; class fenwick { int ft[MAXN + 5]; public: void add(int v, int p) { for (int i=p; i<=MAXN; i+=i&(-i)) {ft[i]+=v;} } int ask(int p) { int res = 0; for (int i=p; i>0; i-=i&(-i)) {res+=ft[i];} return(res); } } BIT; void pairs() { for (int i=1; i<=N; i++) { //init horizontal while (S.size()) {S.pop_back();} for (int j=1; j<=M; j++) { bool same = false; while(S.size() && S.back().first <= A[i][j]) { if (A[i][j] == S.back().first) {same=true;} if (j - S.back().second > 1) {HorM[i].insert({S.back().second, j});} S.pop_back(); } if (!same && S.size() && j - S.back().second > 1) {HorM[i].insert({S.back().second, j});} S.push_back({A[i][j], j}); } } for (int j=1; j<=M; j++) { while (S.size()) {S.pop_back();} for (int i=1; i<=N; i++) { bool same = false; while (S.size() && S.back().first <= A[i][j]) { if (A[i][j] == S.back().first) {same=true;} if (i - S.back().second > 1) {VertM[j].insert({S.back().second,i});} S.pop_back(); } if (!same && S.size() && i - S.back().second > 1) {VertM[j].insert({S.back().second,i});} S.push_back({A[i][j], i}); } } for (int i=N; i>=1; i--) { while (HorM[i].size()) { int pt = i; pair <int,int> p = *HorM[i].begin(); while (HorM[pt].find(p) != HorM[pt].end()) { Hor[pt][p.first].push_back({p.second, i}); //i is goes up to HorM[pt].erase(p), pt--; } } } for (int j=M; j>=1; j--) { while (VertM[j].size()) { int pt = j; pair <int,int> p = *VertM[j].begin(); while (VertM[pt].find(p) != VertM[pt].end()) { Vert[p.first][pt].push_back({j, p.second}); VertM[pt].erase(p), pt--; } } } for (int i=1; i<=N; i++) { for (int j=1; j<=M; j++) { sort(Hor[i][j].begin(), Hor[i][j].end()); sort(Vert[i][j].begin(), Vert[i][j].end()); } } } long long count_rectangles(vector<vector<int> > a) { long long ans = 0; N = a.size(), M = a[0].size(); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { A[i+1][j+1]=a[i][j]; //zero index } } pairs(); for (int i=1; i<=N; i++) { for (int j=1; j<=M; j++) { //(i,j) top left int pt1 = Hor[i+1][j].size()-1, pt2 = Vert[i][j+1].size()-1; //go (i,j+1) for vert and (i+1,j) for hor while (pt1 >= 0 || pt2 >= 0) { if (pt1 == -1 || (pt2 >= 0 && Hor[i+1][j][pt1].first >= Vert[i][j+1][pt2].first)) { BIT.add(1, Vert[i][j+1][pt2].second); pt2--; } else { ans += (long long) BIT.ask(Hor[i+1][j][pt1].second+1) - BIT.ask(i+1); pt1--; } } for (auto v: Vert[i][j+1]) { BIT.add(-1, v.second); } } } 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...