제출 #297977

#제출 시각아이디문제언어결과실행 시간메모리
297977erd1Rectangles (IOI19_rect)C++14
59 / 100
4554 ms1048580 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; template<typename Cmp> struct node{ node *L, *R; int l, r, mid; int cmp(int a, int b){ return Cmp()(a, b)?a:b; } struct inode{ inode *L, *R; int l, r, mid; int val; int cmp(int a, int b){ return Cmp()(a, b)?a:b; } inode(int ll, int rr, const vector<int>& v) : l(ll), r(rr), mid((l+r)/2) { if(l == r)val = v[l]; else L = new inode(l, mid, v), R = new inode(mid+1, r, v), val = cmp(L->val, R->val); } inode(int ll, int rr, inode* n1, inode* n2) : l(ll), r(rr), mid((l+r)/2) { val = cmp(n1->val, n2->val); if(l != r)L = new inode(l, mid, n1->L, n2->L), R = new inode(mid+1, r, n1->R, n2->R); } int query(int ll, int rr){ assert(ll <= r && rr >= l); if(ll <= l && rr >= r)return val; if(ll > mid)return R->query(ll, rr); if(rr <= mid)return L->query(ll, rr); return cmp(L->query(ll, rr), R->query(ll, rr)); } } *data; node(int ll, int rr, int l2, int r2, const vector<vector<int>>& v) : l(ll), r(rr), mid((l+r)/2) { if(l != r) L = new node(l, mid, l2, r2, v), R = new node(mid+1, r, l2, r2, v), data = new inode(l2, r2, L->data, R->data); else data = new inode(l2, r2, v[l]); } int query(int l1, int r1, int l2, int r2){ assert(l1 <= r && r1 >= l); if(l1 <= l && r1 >= r)return data->query(l2, r2); if(l1 > mid)return R->query(l1, r1, l2, r2); if(r1 <= mid)return L->query(l1, r1, l2, r2); return cmp(L->query(l1, r1, l2, r2), R->query(l1, r1, l2, r2)); } }; node<greater<int>> *d, *r; node<less<int>> *u, *l; set<tuple<int, int, int, int>> st; 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}); } } u = new node<less<int>>(0, n-1, 0, m-1, U), l = new node<less<int>>(0, n-1, 0, m-1, L); d = new node<greater<int>>(0, n-1, 0, m-1, D), r = new node<greater<int>>(0, n-1, 0, m-1, R); 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] << " " << u->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) << endl; if(u->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != U[i][j])goto next; if(l->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != L[i][j])goto next; if(d->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != D[i][j])goto next; if(r->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != R[i][j])goto next; st.insert({U[i][j], L[i][j], D[i][j], R[i][j]}); next:; } return st.size(); }
#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...