Submission #297939

#TimeUsernameProblemLanguageResultExecution timeMemory
297939erd1Rectangles (IOI19_rect)C++14
23 / 100
823 ms159480 KiB
#include "rect.h" #include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define all(x) (x).begin(), (x).end() typedef int64_t lld; typedef pair<int, int> pii; /* #include<bits/extc++.h> using namespace __gnu_pbds; template<typename T, typename comp = greater<T>> using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>; */ template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> p){ return out << "(" << p.ff << ", " << p.ss << ")"; } vector<pii> tmp; vector<vector<int>> U, D, L, R; long long count_rectangles(vector<vector<int>> a) { int n = a.size(), m = a[0].size(); U = D = L = R = a; for(int i = 1; i < n; i++){ tmp.resize(0); tmp.pb({INT_MAX, -1}); for(int j = 0; j < m; j++){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); L[i][j] = tmp.back().ss; tmp.pb({a[i][j], j}); } tmp.resize(0); tmp.pb({INT_MAX, m}); for(int j = m-1; j > 0; j--){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); R[i][j] = tmp.back().ss; tmp.pb({a[i][j], j}); } } for(int j = 1; j < m; j++){ tmp.resize(0); tmp.pb({INT_MAX, -1}); for(int i = 0; i < n; i++){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); U[i][j] = tmp.back().ss; tmp.pb({a[i][j], i}); } tmp.resize(0); tmp.pb({INT_MAX, n}); for(int i = n-1; i > 0; i--){ while(tmp.back().ff <= a[i][j])tmp.pop_back(); D[i][j] = tmp.back().ss; tmp.pb({a[i][j], i}); } } int ans = 0; for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++){ if(U[i][j] < 0 || D[i][j] >= n || L[i][j] < 0 || R[i][j] >= m)goto next; //cout << i << " " << j << " " << U[i][j] << D[i][j] << L[i][j] << R[i][j] << endl; for(int x = U[i][j]+1; x < D[i][j]; x++) for(int y = L[i][j]+1; y < R[i][j]; y++){ //cout << " " << x << " " << y << endl; if(!(U[i][j] <= U[x][y] && D[i][j] >= D[x][y] && L[i][j] <= L[x][y] && R[i][j] >= R[x][y]))goto next; if(a[i][j] == a[x][y] && (x > i || x == i && y > j))goto next; } //cout << i << " " << j << endl; ans++; next:; } return ans; }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:66:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |      if(a[i][j] == a[x][y] && (x > i || x == i && y > j))goto next;
      |                                         ~~~~~~~^~~~~~~~
#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...