Submission #405153

#TimeUsernameProblemLanguageResultExecution timeMemory
405153rocks03Rectangles (IOI19_rect)C++14
10 / 100
166 ms996 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) x.begin(), x.end() #define debug(x) cout << #x << ": " << x << " " #define nl cout << "\n" #define rep(i, a, b) for(int i = (a); i < (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); long long count_rectangles(vector<vector<int>> a){ int N = SZ(a), M = SZ(a[0]); vector<int> rt[N][M], dw[N][M]; rep(i, 0, N){ vector<int> st; per(j, M - 1, 0){ while(!st.empty() && a[i][j] > a[i][st.back()]){ if(j + 1 < st.back()) rt[i][j].pb(st.back()); st.pop_back(); } if(!st.empty() && j + 1 < st.back()) rt[i][j].pb(st.back()); st.pb(j); } } rep(j, 0, M){ vector<int> st; per(i, N - 1, 0){ while(!st.empty() && a[i][j] > a[st.back()][j]){ if(i + 1 < st.back()) dw[i][j].pb(st.back()); st.pop_back(); } if(!st.empty() && i + 1 < st.back()) dw[i][j].pb(st.back()); st.pb(i); } } ll ans = 0; rep(i, 1, N - 1){ rep(j, 0, M){ int curj = j + 1; set<int> st1; if(i - 1 >= 0 && j + 1 < M){ for(int i2 : dw[i - 1][j + 1]) st1.insert(i2); } for(int j2 : rt[i][j]){ while(curj < j2){ set<int> st2; for(int i2 : dw[i - 1][curj]){ if(!st1.count(i2)) continue; st2.insert(i2); } st1 = st2; if(min(a[i - 1][curj], a[i + 1][curj]) > a[i][curj]) curj++; else{ curj = -1; break; } } if(curj == -1 || !SZ(st1)) break; if(j2 - j > 2){ ans += SZ(st1); } } } } rep(j, 1, M - 1){ rep(i, 0, N){ int curi = i + 1; for(int i2 : dw[i][j]){ while(curi < i2){ if(min(a[curi][j - 1], a[curi][j + 1]) > a[curi][j]) curi++; else{ curi = -1; break; } } if(curi == -1) break; ans += 1; } } } 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...