Submission #937444

#TimeUsernameProblemLanguageResultExecution timeMemory
937444GrindMachineRectangles (IOI19_rect)C++17
100 / 100
2731 ms659332 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* read some solutions long back, remember some ideas from there */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "rect.h" template<typename T> struct fenwick { int siz; vector<T> tree; fenwick() { } fenwick(int n) { siz = n; tree = vector<T>(n + 1); } int lsb(int x) { return x & -x; } void build(vector<T> &a, int n) { for (int i = 1; i <= n; ++i) { int par = i + lsb(i); tree[i] += a[i]; if (par <= siz) { tree[par] += tree[i]; } } } void pupd(int i, T v) { i++; while (i <= siz) { tree[i] += v; i += lsb(i); } } T sum(int i) { i++; T res = 0; while (i) { res += tree[i]; i -= lsb(i); } return res; } T query(int l, int r) { if (l > r) return 0; T res = sum(r) - sum(l - 1); return res; } }; long long count_rectangles(std::vector<std::vector<int> > a) { int n = sz(a), m = sz(a[0]); if(n <= 2 or m <= 2) return 0; vector<pii> up[n][m]; int ptr = 0; rep(j,m){ stack<int> st; rep(i,n){ bool eq = false; while(!st.empty() and a[i][j] >= a[st.top()][j]){ int k = st.top(); st.pop(); if(a[i][j] == a[k][j]){ eq = true; } if(i-k >= 2){ up[i][j].pb({k,ptr++}); } } if(!st.empty() and !eq){ int k = st.top(); if(i-k >= 2){ up[i][j].pb({k,ptr++}); } } st.push(i); } } vector<int> farthest(ptr); int seg_ptr[n][n]; memset(seg_ptr,-1,sizeof seg_ptr); rev(j,m-1,0){ if(j+2 < m){ rep(i,n){ for(auto [k,ptr] : up[i][j+2]){ seg_ptr[k][i] = -1; } } } if(j+1 < m){ rep(i,n){ for(auto [k,ptr] : up[i][j+1]){ seg_ptr[k][i] = ptr; } } } rep(i,n){ for(auto [k,ptr] : up[i][j]){ if(seg_ptr[k][i] != -1){ farthest[ptr] = farthest[seg_ptr[k][i]]; } else{ farthest[ptr] = j; } } } } int prev_occ[m][m], first_occ[m][m]; memset(prev_occ,-1,sizeof prev_occ); memset(first_occ,-1,sizeof first_occ); ll ans = 0; vector<int> queries[ptr]; rep1(i,n-2){ stack<int> st; vector<pii> good; rep(j,m){ bool eq = false; while(!st.empty() and a[i][j] >= a[i][st.top()]){ int k = st.top(); st.pop(); if(a[i][j] == a[i][k]){ eq = true; } if(j-k >= 2){ good.pb({k,j}); } } // cout << j << endl; // cout << eq << endl; // auto st_copy = st; // while(!st_copy.empty()){ // cout << st_copy.top() << " "; // st_copy.pop(); // } // cout << endl; if(!st.empty() and !eq){ int k = st.top(); if(j-k >= 2){ // cout << k << " " << j << endl; good.pb({k,j}); } } st.push(j); } for(auto [l,r] : good){ if(prev_occ[l][r] != i-1){ first_occ[l][r] = i; } prev_occ[l][r] = i; int lo = 0, hi = sz(up[i+1][l+1])-1; int pos = -1; while(lo <= hi){ int mid = (lo+hi) >> 1; if(up[i+1][l+1][mid].ff >= first_occ[l][r]-1){ pos = mid; lo = mid+1; } else{ hi = mid-1; } } if(pos != -1){ int ind = up[i+1][l+1][pos].ss; queries[ind].pb(r); } /* for(auto [k,ptr] : up[i+1][l+1]){ if(k >= first_occ[l][r]-1){ if(farthest[ptr] >= r-1){ ans++; } } else{ break; } } */ } } fenwick<int> fenw(m); rep(i,n){ rep(j,m){ for(auto [k,ptr] : up[i][j]){ fenw.pupd(farthest[ptr],1); trav(r,queries[ptr]){ ans += fenw.query(r-1,m-1); } } for(auto [k,ptr] : up[i][j]){ fenw.pupd(farthest[ptr],-1); } } } /* int oans = 0; rep1(i1,n-2){ rep1(j1,m-2){ for(int i2 = i1; i2 < n-1; ++i2){ for(int j2 = j1; j2 < m-1; ++j2){ bool ok = true; for(int r = i1; r <= i2; ++r){ for(int c = j1; c <= j2; ++c){ if(a[r][c] >= min({a[i1-1][c],a[i2+1][c],a[r][j1-1],a[r][j2+1]})){ ok = false; break; } } if(!ok) break; } if(ok){ oans++; cout << i1 << " " << j1 << " " << i2 << " " << j2 << endl; } } } } } */ // cout << ans << endl; // cout << oans << endl; // cout << endl; // assert(ans == oans); 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...