Submission #1029281

#TimeUsernameProblemLanguageResultExecution timeMemory
1029281onbertRectangles (IOI19_rect)C++17
8 / 100
750 ms299104 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ss short #define ll long long struct range { ss r, mx; }; bool cmp0(range &a, range &b) {return a.r > b.r;} bool cmp1(range &a, range &b) {return a.mx > b.mx;} const int maxn = 2505, INF = 2505, lg = 12; int n, m; vector<vector<vector<pair<ss,ss>>>> pos[2]; vector<vector<vector<range>>> start[2]; ss fen[maxn]; void update(int id, int val) { while (id<maxn) { fen[id] += val; id += (id & -id); } } int qry(int id) { int val = 0; while (id >= 1) { val += fen[id]; id -= (id & -id); } return val; } pair<int,int> st[maxn][lg]; int qry1(int l, int r) { int lg = log2(r-l+1); pair<int,int> lhs = st[l][lg], rhs = st[r-(1<<lg)+1][lg]; if (rhs.first > lhs.first) return rhs.second; else return lhs.second; } int nn, II, ii; void dfs(int l, int r) { if (l>r) return; int mid = qry1(l, r); // if (II==0 && ii==1) cout << l << " " << r << " " << mid << endl; if (l>=1 && r<=nn-1 && st[mid][0].first < st[l-1][0].first && st[mid][0].first < st[r+1][0].first) { // if (II==1) cout << ii << " " << l << " " << r << endl; pos[II][l][r-l].push_back({(ss)ii, -1}); if (II==0) start[II][ii][l].push_back({(ss)r, -1}); else start[II][l][ii].push_back({(ss)r, -1}); } dfs(l, mid-1); dfs(mid+1, r); } long long count_rectangles(vector<vector<int32_t>> a) { n = a.size(), m = a[0].size(); pos[0].resize(m); for (int i=0;i<m;i++) pos[0][i].resize(m - i); pos[1].resize(n); for (int i=0;i<n;i++) pos[1][i].resize(n - i); start[0].resize(n); start[1].resize(n); for (int i=0;i<n;i++) start[0][i].resize(m), start[1][i].resize(m); nn = m, II = 0; for (int i=0;i<n;i++) { ii = i; for (int j=m-1;j>=0;j--) { st[j][0] = {a[i][j], j}; for (int k=1;k<lg;k++) { if (j+(1<<k)-1 < m) { st[j][k] = st[j][k-1]; pair<int,int> nxt = st[j + (1 << (k-1))][k-1]; if (nxt.first > st[j][k].first) st[j][k] = nxt; } else break; } } dfs(0, m-1); } nn = n, II = 1; for (int j=0;j<m;j++) { ii = j; for (int i=n-1;i>=0;i--) { st[i][0] = {a[i][j], i}; for (int k=1;k<lg;k++) { if (i+(1<<k)-1 < n) { st[i][k] = st[i][k-1]; pair<int,int> nxt = st[i + (1 << (k-1))][k-1]; if (nxt.first > st[i][k].first) st[i][k] = nxt; } else break; } } dfs(0, n-1); } for (int I=0;I<=1;I++) { int nn = m; if (I==1) nn = n; for (int l=0;l<nn;l++) for (int r=l;r<nn;r++) { sort(pos[I][l][r-l].begin(), pos[I][l][r-l].end()); int sz = pos[I][l][r-l].size(); for (int i=sz-1;i>=0;i--) { if (i==sz-1 || pos[I][l][r-l][i+1].first!=pos[I][l][r-l][i].first+1) pos[I][l][r-l][i].second = pos[I][l][r-l][i].first; else pos[I][l][r-l][i].second = pos[I][l][r-l][i+1].second; } } } for (int I=0;I<=1;I++) { for (int i=0;i<n;i++) for (int j=0;j<m;j++) { for (auto &[r, mx]:start[I][i][j]) { ss x = j, y = i; if (I==1) x = i, y = j; mx = (*lower_bound(pos[I][x][r-x].begin(), pos[I][x][r-x].end(), make_pair(y, (ss)-1))).second; } } } ll ans = 0; vector<int> LOG; for (int i=1;i<n-1;i++) for (int j=1;j<m-1;j++) { sort(start[0][i][j].begin(), start[0][i][j].end(), cmp0); sort(start[1][i][j].begin(), start[1][i][j].end(), cmp1); int pt = -1; LOG.clear(); for (auto [r, mx]:start[0][i][j]) { while (pt+1 < start[1][i][j].size() && start[1][i][j][pt+1].mx >= r) { pt++; update(start[1][i][j][pt].r, 1); LOG.push_back(start[1][i][j][pt].r); } ans += qry(mx); } for (int x:LOG) update(x, -1); } return ans; }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:124:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             while (pt+1 < start[1][i][j].size() && start[1][i][j][pt+1].mx >= r) {
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...