제출 #430046

#제출 시각아이디문제언어결과실행 시간메모리
430046egekabasRectangles (IOI19_rect)C++14
0 / 100
17 ms25804 KiB
#include "rect.h" #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<int, int> pii; typedef pair<ld, ld> pld; int bit[2509][2509]; int bitsz; void upd(int x, int y, int val){ for(int i1 = x+1; i1 > 0; i1 -= i1&(-i1)) for(int i2 = y+1; i2 <= bitsz; i2 += i2&(-i2)) bit[i1][i2] += val; } int get(int x, int y){ int ret = 0; for(int i1 = x+1; i1 <= bitsz; i1 += i1&(-i1)) for(int i2 = y+1; i2 > 0; i2 -= i2&(-i2)) ret += bit[i1][i2]; return ret; } ll pickdouble(int n){ return ll(n)*(n+1)/2; } long long count_rectangles(std::vector<std::vector<int> > a) { int n = a.size(), m = a[0].size(); bitsz = max(n, m); for(int i = 1; i <= bitsz; ++i) for(int j = 1; j <= bitsz; ++j) bit[i][j] = 0; vector<set<pii>> pos(n); for(int i = 0; i < n; ++i){ vector<int> cur; for(int j = m-1; j >= 0; --j){ while(cur.size() && a[i][cur.back()] < a[i][j]){ pos[i].insert({j, cur.back()}); cur.pop_back(); } if(cur.size()) pos[i].insert({j, cur.back()}); cur.pb(j); } } vector<vector<pair<pii, int>>> maxval(m); for(int i = 0; i < n; ++i) for(auto u : pos[i]){ int j; for(j = i+1; j < n; ++j){ auto it = pos[j].lower_bound(u); if(it == pos[j].end() || *it != u) break; pos[j].erase(it); } --j; if(u.ss-u.ff > 1) maxval[u.ff].pb({{i, j}, u.ss}); //cout << u.ff << ' ' << u.ss << ' ' << i << ' ' << j << '\n'; } pos = vector<set<pii>>(m); for(int i = 0; i < m; ++i){ vector<int> cur; for(int j = n-1; j >= 0; --j){ while(cur.size() && a[cur.back()][i] < a[j][i]){ pos[i].insert({j, cur.back()}); cur.pop_back(); } if(cur.size()) pos[i].insert({j, cur.back()}); cur.pb(j); } } vector<vector<pair<pii, int>>> fin(m); for(int i = 0; i < m; ++i) for(auto u : pos[i]){ int j; for(j = i+1; j < m; ++j){ auto it = pos[j].lower_bound(u); if(it == pos[j].end() || *it != u) break; pos[j].erase(it); } --j; if(u.ss-u.ff > 1) for(int k = i; k <= j; ++k) fin[k].pb({{u.ff, u.ss}, j}); } ll ans = 0; for(int i = 1; i < m; ++i){ sort(all(fin[i])); sort(all(maxval[i-1])); int curidx = 0; for(auto u : fin[i]){ while(curidx < (int)maxval[i-1].size() && maxval[i-1][curidx].ff.ff <= u.ff.ff+1){ upd(maxval[i-1][curidx].ff.ss, maxval[i-1][curidx].ss, 1); ++curidx; } int val = get(u.ff.ss-1, u.ss+1); //cout << i << ' ' << u.ss << ' ' << u.ff.ff << ' ' << u.ff.ss << ' ' << val << '\n'; ans += val; } for(int j = 0; j < curidx; ++j) upd(maxval[i-1][j].ff.ss, maxval[i-1][j].ss, -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...