제출 #405763

#제출 시각아이디문제언어결과실행 시간메모리
405763rocks03Rectangles (IOI19_rect)C++14
13 / 100
1594 ms608564 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 - 1){ 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()); if(!st.empty() && a[i][j] == a[i][st.back()]) st.pop_back(); st.pb(j); } } rep(j, 0, M - 1){ 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()); if(!st.empty() && a[i][j] == a[st.back()][j]) st.pop_back(); st.pb(i); } } ll ans = 0; vector<pii> vt[M][M]; rep(i, 0, N - 1){ rep(j, 0, M - 1){ for(int j2 : rt[i][j]){ if(SZ(vt[j][j2]) && vt[j][j2].back().ss == i - 1) vt[j][j2].back().ss = i; else vt[j][j2].pb({i, i}); } } } rep(i, 1, N - 2){ rep(j, 0, M - 1){ int curj = j + 1; vector<int> st; for(int i2 : dw[i - 1][j + 1]) st.pb(i2); for(int j2 : rt[i][j]){ if(!SZ(st)) break; while(curj < j2){ vector<int> st2; if(SZ(dw[i - 1][curj]) < SZ(st)){ for(int i2 : dw[i - 1][curj]){ int p = lower_bound(all(st), i2) - st.begin(); if(p < SZ(st) && st[p] == i2) st2.pb(i2); } } else{ for(int i2 : st){ int p = lower_bound(all(dw[i - 1][curj]), i2) - dw[i - 1][curj].begin(); if(p < SZ(dw[i - 1][curj]) && dw[i - 1][curj][p] == i2) st2.pb(i2); } } st = st2; curj++; } vector<int> st2; for(int i2 : st){ int p = upper_bound(all(vt[j][j2]), make_pair(i2, -1)) - vt[j][j2].begin() - 1; if(p >= 0 && vt[j][j2][p].ff <= i && i2 - 1 <= vt[j][j2][p].ss){ ans += 1; st2.pb(i); } else break; } st = st2; } } } 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...