Submission #1242906

#TimeUsernameProblemLanguageResultExecution timeMemory
1242906AMnuRectangles (IOI19_rect)C++20
100 / 100
1463 ms610600 KiB
#include "rect.h" #include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int MAXN = 2505; int N, M, fen[MAXN]; ll ans; pii B[MAXN][MAXN]; vector <pii> C[2][MAXN][MAXN]; int pref(int x) { int sum = 0; for (int i=x;i;i-=i&-i) { sum += fen[i]; } return sum; } void add(int x,int y) { for (int i=x;i<MAXN;i+=i&-i) { fen[i] += y; } } void reset() { for (int i=0;i<MAXN;i++) { for (int j=i+2;j<MAXN;j++) { B[i][j] = {-1,-1}; } } } void get(int i,int x,int y,int t) { if (y-x == 1) return; if (B[x][y].se == i-1) { B[x][y].se++; } else { B[x][y] = {i,i}; } C[t][i][y-1].push_back({x+1,B[x][y].fi}); } void solve(int x,int y) { vector <pii> &A = C[0][x][y]; vector <pii> &B = C[1][y][x]; for (pii &x : B) { swap(x.fi,x.se); } sort(A.begin(),A.end()); sort(B.begin(),B.end()); int j=0; for (int i=0;i<(int)A.size();i++) { while (j<(int)B.size() && B[j].fi<=A[i].fi) { add(B[j].se,1); j++; } ans += j-pref(A[i].se-1); } for (int i=0;i<j;i++) { add(B[i].se,-1); } } ll count_rectangles(vector<vector<int> > A) { N = A.size(); M = A[0].size(); reset(); for (int i=1;i<N-1;i++) { stack <pii> S; for (int j=0;j<M;j++) { while (!S.empty() && S.top().fi < A[i][j]) { get(i,S.top().se,j,0); S.pop(); } if (!S.empty()) { get(i,S.top().se,j,0); if (S.top().fi == A[i][j]) { S.pop(); } } S.push({A[i][j],j}); } } reset(); for (int i=1;i<M-1;i++) { stack <pii> S; for (int j=0;j<N;j++) { while (!S.empty() && S.top().fi < A[j][i]) { get(i,S.top().se,j,1); S.pop(); } if (!S.empty()) { get(i,S.top().se,j,1); if (S.top().fi == A[j][i]) { S.pop(); } } S.push({A[j][i],j}); } } for (int i=1;i<N-1;i++) { for (int j=1;j<M-1;j++) { if (!C[0][i][j].empty() && !C[1][j][i].empty()) { solve(i,j); } } } 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...