| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 950582 |
2024-03-20T12:52:06 Z |
qin |
Rectangles (IOI19_rect) |
C++17 |
|
4 ms |
1628 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1; // PAMIETAC, ZE TAM MAM CIAG INDEKSOWANY OD 0
struct segminmax{
int base;
struct Node{
int mn, mx;
Node(){ mn = inf, mx = 0; }
};
vv<Node> t;
void init(int n, vv<int> &a, vv<int> &b){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, Node());
for(int i = 1; i <= n; ++i) t[i+base-1].mn = b[i-1], t[i+base-1].mx = a[i-1];
for(int i = base-1; i; --i) t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn), t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
}
int query_interval_min(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i].mn;
int mid = (s+e)>>1, result = inf;
if(x <= mid) result = min(result, query_interval_min(i<<1, s, mid, x, y));
if(mid < y) result = min(result, query_interval_min(i<<1|1, mid+1, e, x, y));
return result;
}
int query_interval_max(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i].mx;
int mid = (s+e)>>1, result = 0;
if(x <= mid) result = max(result, query_interval_max(i<<1, s, mid, x, y));
if(mid < y) result = max(result, query_interval_max(i<<1|1, mid+1, e, x, y));
return result;
}
int query_min(int l, int r){
if(l <= r) return query_interval_min(1, 1, base, max(1, l), min(base, r));
return 0;
}
int query_max(int l, int r){
if(l <= r) return query_interval_max(1, 1, base, max(1, l), min(base, r));
return 0;
}
};
struct seg{
int base;
vv<int> t;
void init(int n){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, 0);
}
void update(int i, int val){
for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = t[i<<1]+t[i<<1|1];
}
int query_interval(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i];
int mid = (s+e)>>1, result = 0;
if(x <= mid) result += query_interval(i<<1, s, mid, x, y);
if(mid < y) result += query_interval(i<<1|1, mid+1, e, x, y);
return result;
}
int query(int l, int r){
if(l <= r) return query_interval(1, 1, base, max(1, l), min(base, r));
return 0;
}
};
ll count_rectangles(vv<vv<int>> t){
int n = ssize(t), m = ssize(t[0]);
vv<vv<int>> u(n, vv<int>(m, 0)), d(n, vv<int>(m, n-1));
vv<map<pii, int>> mp(n);
vv<int> st;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){ // przedzialy gdzie ja to prawy koniec
while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
if(ssize(st)) mp[i][pii(st.back(), j)] = 1;
st.emplace_back(j);
} st = vv<int>();
for(int j = m-1; ~j; --j){ // przedzialy gdzie ja to lewy koniec
while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
if(ssize(st)) mp[i][pii(j, st.back())] = 1;
st.emplace_back(j);
} st = vv<int>();
}
for(int j = 0; j < m; ++j){
for(int i = 0; i < n; ++i){ // przedzialy gdzie ja to dolny koniec (ustawiamy najblizszego do gory)
while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
if(ssize(st)) u[i][j] = st.back();
st.emplace_back(i);
} st = vv<int>();
for(int i = n-1; ~i; --i){ // przedzialy gdzie ja to gorny koniec (ustawiamy najblizszego na dole)
while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
if(ssize(st)) d[i][j] = st.back();
st.emplace_back(i);
} st = vv<int>();
}
//~ for(int i = 0; i < n; ++i){
//~ for(int j = 0; j < m; ++j) printf("%d ", d[i][j]);
//~ pn;
//~ }
ll result = 0;
vv<segminmax> segm(n);
for(int i = 0; i < n; ++i) segm[i].init(m, u[i], d[i]);
for(int i = 1; i < n-1; ++i){
for(pair<pii, int> pd : mp[i]) if(pd.se){
int l = pd.fi.fi+1, r = pd.fi.se-1;
if(r < l) continue;
++l, ++r; // do przedzialowca
int sz = 1;
for(int j = i+1; j < n-1; ++j) if(mp[j][pd.fi]) ++sz, mp[j][pd.fi] = 0;
else break;
seg seg; seg.init(sz);
vv<vv<int>> rem(sz);
for(int j = i; j < i+sz; ++j){
for(int &x : rem[j-i]) seg.update(x, 0);
int endpoint = segm[j-1].query_min(l, r);
if(j >= endpoint) continue;
seg.update(j-i+1, 1);
if(endpoint-i < sz) rem[endpoint-i].emplace_back(j-i+1);
endpoint = segm[j+1].query_max(l, r);
result += seg.query(max(0, endpoint-i)+1, j);
}
}
}
return result;
}
#ifdef LOCAL
int main(){
int T = 1;
for(++T; --T; ){
int n, m; scanf("%d%d", &n, &m);
vv<vv<int>> t(n, vv<int>(m, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j) scanf("%d", &t[i][j]);
ll result = count_rectangles(t);
printf("%lld\n", result);
}
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
1604 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
