oj.uz

Submission #836939

# Submission time Handle Problem Language Result Execution time Memory
836939 2023-08-24T17:30:23 Z winter0101 Rectangles (IOI19_rect) C++17
100 / 100
 2905 ms 318556 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e3+5e2+9;
const int inf=7e6+9;
struct ST{
vector<int>mx,mn;
void resz(int n){
mx.resize(4*n+9);
mn.resize(4*n+9);
}
void upmin(int id,int l,int r,int u,int v1){
if (l>u||r<u)return;
if (l==r){
    //mx[id]=v2;
    mn[id]=v1;
    return;
}
int mid=(l+r)/2;
upmin(id*2,l,mid,u,v1);
upmin(id*2+1,mid+1,r,u,v1);
mn[id]=min(mn[id*2],mn[id*2+1]);
}
void upmax(int id,int l,int r,int u,int v2){
if (l>u||r<u)return;
if (l==r){
    mx[id]=v2;
    return;
}
int mid=(l+r)/2;
upmax(id*2,l,mid,u,v2);
upmax(id*2+1,mid+1,r,u,v2);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
int getmin(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 2509;
if (u<=l&&r<=v)return mn[id];
int mid=(l+r)/2;
return min(getmin(id*2,l,mid,u,v),getmin(id*2+1,mid+1,r,u,v));
}
int getmax(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return mx[id];
int mid=(l+r)/2;
return max(getmax(id*2,l,mid,u,v),getmax(id*2+1,mid+1,r,u,v));
}
};
struct BIT{
vector<int>bit;
int n;
void resz(int _n){
n=_n;
bit.resize(n+1);
}
void add(int pos,int val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int m,n;
int up[maxn][maxn],down[maxn][maxn],a[maxn][maxn];
pii l[maxn][maxn],r[maxn][maxn];
//fi min se max
ST st;
int b[maxn][maxn],c[maxn][maxn];
vector<int>del[maxn];
void build(){
//up[i][j]=i1 j i1<i a[i1][j]>=a[i][j]
st.resz(n);
for1(j,1,n){
stack<int>t;
t.push(0);
a[0][j]=inf;
for1(i,1,m){
while (!t.empty()&&a[t.top()][j]<a[i][j])t.pop();
up[i][j]=t.top();
t.push(i);
}
}
for1(j,1,n){
a[m+1][j]=inf;
stack<int>t;
t.push(m+1);
for2(i,m,1){
while (!t.empty()&&a[t.top()][j]<a[i][j])t.pop();
down[i][j]=t.top();
t.push(i);
}
}
for1(i,1,m){
a[i][n+1]=inf;
stack<int>t;
t.push(n+1);
for2(j,n,1){
while (!t.empty()&&a[i][t.top()]<a[i][j])t.pop();
//cout<<i<<" "<<j<<" "<<t.top()<<'\n';
//b[i][t.top()].insert(j);
c[i][j]=t.top();
t.push(j);
}
}
for1(i,1,m){
a[i][0]=inf;
stack<int>t;
t.push(0);
for1(j,1,n){
while (!t.empty()&&a[i][t.top()]<a[i][j])t.pop();
//if (t.top()!=0){
//b[i][j].insert(t.top());
b[i][j]=t.top();
//}
t.push(j);
}
}
for1(i,1,m-1){
for1(j,1,n){
st.upmin(1,1,n,j,down[i][j]);
}
for1(j,1,n){
//min
l[i+1][j].fi=st.getmin(1,1,n,b[i+1][j]+1,j-1);
r[i+1][j].fi=st.getmin(1,1,n,j+1,c[i+1][j]-1);
}
}
for1(i,2,m){
for1(j,1,n){
st.upmax(1,1,n,j,up[i][j]);
}
for1(j,1,n){
l[i-1][j].se=st.getmax(1,1,n,b[i-1][j]+1,j-1);
r[i-1][j].se=st.getmax(1,1,n,j+1,c[i-1][j]-1);
}
}
}
BIT bit;
long long ans=0;
bool check(int i,int l1,int r1){
if (c[i][l1]>=r1&&b[i][r1]<=l1)return 1;
return 0;
}
void solve(int i,int l1,int r1){
if (i>2&&check(i-1,l1,r1))return;
if (l1==0||r1==n+1)return;
int p=i;
for1(k,i,m-1){
if (check(k,l1,r1))p=k;
else break;
}
if (r1-l1+1-2<=0)return;
//ans=0;
for2(k,p,i){
int vdcot;
if (a[k][l1]>=a[k][r1])vdcot=l[k][r1].se;
if (a[k][l1]<=a[k][r1])vdcot=r[k][l1].se;
vdcot=max(vdcot+1,i);
if (vdcot<=k){
bit.add(k,1);
del[vdcot].pb(k);
}
int maxcot;
if (a[k][l1]>=a[k][r1])maxcot=l[k][r1].fi;
if (a[k][l1]<=a[k][r1])maxcot=r[k][l1].fi;
maxcot=min(maxcot-1,p);
ans+=1ll*bit.get(i,maxcot);
for (auto v1:del[k])bit.add(v1,-1);
del[k].clear();
}
//cout<<i<<" "<<p<<" "<<l1+1<<" "<<r1-1<<" "<<ans<<'\n';
}
long long count_rectangles(vector<vector<int>>a1){
m=a1.size();
for1(i,0,m-1){
n=a1[i].size();
for1(j,0,n-1){
a[i+1][j+1]=a1[i][j];
}
}
build();
bit.resz(m);
for1(i,2,m-1){
for1(j,1,n){
solve(i,b[i][j],j);
//cout<<i<<" "<<b[i][j]<<" "<<j<<'\n';
if (a[i][c[i][j]]!=a[i][j])solve(i,j,c[i][j]);
}
}
//cout<<ans<<'\n';
return ans;
}
/*signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("temp.INP","r",stdin);
    //freopen(".OUT","w",stdout);
	int n1, m1;
	cin>>n1>>m1;
	vector<vector<int>> a1(n1, vector<int>(m1));
	for (int i = 0; i < n1; i++)	{
		for (int j = 0; j < m1; j++) {
			cin>>a1[i][j];
		}
	}
	long long result = count_rectangles(a1);
	printf("%lld\n", result);
	return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 644 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1 ms 1240 KB Output is correct
21 Correct 1 ms 596 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 644 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1 ms 1240 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 2 ms 2900 KB Output is correct
23 Correct 3 ms 2900 KB Output is correct
24 Correct 3 ms 2900 KB Output is correct
25 Correct 4 ms 2900 KB Output is correct
26 Correct 3 ms 2900 KB Output is correct
27 Correct 3 ms 2900 KB Output is correct
28 Correct 3 ms 2900 KB Output is correct
29 Correct 2 ms 2772 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 644 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 2900 KB Output is correct
18 Correct 3 ms 2900 KB Output is correct
19 Correct 3 ms 2900 KB Output is correct
20 Correct 4 ms 2900 KB Output is correct
21 Correct 3 ms 2900 KB Output is correct
22 Correct 3 ms 2900 KB Output is correct
23 Correct 3 ms 2900 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 1236 KB Output is correct
28 Correct 1 ms 1240 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 11 ms 7980 KB Output is correct
31 Correct 12 ms 7892 KB Output is correct
32 Correct 13 ms 8020 KB Output is correct
33 Correct 11 ms 7764 KB Output is correct
34 Correct 15 ms 7892 KB Output is correct
35 Correct 17 ms 8020 KB Output is correct
36 Correct 14 ms 8020 KB Output is correct
37 Correct 15 ms 8020 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 644 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 2900 KB Output is correct
18 Correct 3 ms 2900 KB Output is correct
19 Correct 3 ms 2900 KB Output is correct
20 Correct 4 ms 2900 KB Output is correct
21 Correct 3 ms 2900 KB Output is correct
22 Correct 3 ms 2900 KB Output is correct
23 Correct 3 ms 2900 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 11 ms 7980 KB Output is correct
26 Correct 12 ms 7892 KB Output is correct
27 Correct 13 ms 8020 KB Output is correct
28 Correct 11 ms 7764 KB Output is correct
29 Correct 15 ms 7892 KB Output is correct
30 Correct 17 ms 8020 KB Output is correct
31 Correct 14 ms 8020 KB Output is correct
32 Correct 15 ms 8020 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 1236 KB Output is correct
36 Correct 1 ms 1240 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 146 ms 44404 KB Output is correct
39 Correct 136 ms 44488 KB Output is correct
40 Correct 140 ms 44388 KB Output is correct
41 Correct 133 ms 44364 KB Output is correct
42 Correct 168 ms 44492 KB Output is correct
43 Correct 170 ms 44416 KB Output is correct
44 Correct 169 ms 44800 KB Output is correct
45 Correct 163 ms 42060 KB Output is correct
46 Correct 122 ms 42188 KB Output is correct
47 Correct 143 ms 42172 KB Output is correct
48 Correct 197 ms 43036 KB Output is correct
49 Correct 198 ms 44900 KB Output is correct
50 Correct 96 ms 32500 KB Output is correct
51 Correct 102 ms 22680 KB Output is correct
52 Correct 186 ms 43980 KB Output is correct
53 Correct 193 ms 44988 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 5 ms 848 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1240 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 861 ms 137640 KB Output is correct
8 Correct 1950 ms 281284 KB Output is correct
9 Correct 1945 ms 282820 KB Output is correct
10 Correct 1932 ms 282756 KB Output is correct
11 Correct 574 ms 139840 KB Output is correct
12 Correct 1179 ms 278932 KB Output is correct
13 Correct 1255 ms 282736 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 644 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 2900 KB Output is correct
18 Correct 3 ms 2900 KB Output is correct
19 Correct 3 ms 2900 KB Output is correct
20 Correct 4 ms 2900 KB Output is correct
21 Correct 3 ms 2900 KB Output is correct
22 Correct 3 ms 2900 KB Output is correct
23 Correct 3 ms 2900 KB Output is correct
24 Correct 2 ms 2772 KB Output is correct
25 Correct 11 ms 7980 KB Output is correct
26 Correct 12 ms 7892 KB Output is correct
27 Correct 13 ms 8020 KB Output is correct
28 Correct 11 ms 7764 KB Output is correct
29 Correct 15 ms 7892 KB Output is correct
30 Correct 17 ms 8020 KB Output is correct
31 Correct 14 ms 8020 KB Output is correct
32 Correct 15 ms 8020 KB Output is correct
33 Correct 146 ms 44404 KB Output is correct
34 Correct 136 ms 44488 KB Output is correct
35 Correct 140 ms 44388 KB Output is correct
36 Correct 133 ms 44364 KB Output is correct
37 Correct 168 ms 44492 KB Output is correct
38 Correct 170 ms 44416 KB Output is correct
39 Correct 169 ms 44800 KB Output is correct
40 Correct 163 ms 42060 KB Output is correct
41 Correct 122 ms 42188 KB Output is correct
42 Correct 143 ms 42172 KB Output is correct
43 Correct 197 ms 43036 KB Output is correct
44 Correct 198 ms 44900 KB Output is correct
45 Correct 96 ms 32500 KB Output is correct
46 Correct 102 ms 22680 KB Output is correct
47 Correct 186 ms 43980 KB Output is correct
48 Correct 193 ms 44988 KB Output is correct
49 Correct 3 ms 852 KB Output is correct
50 Correct 2 ms 852 KB Output is correct
51 Correct 1 ms 852 KB Output is correct
52 Correct 1 ms 592 KB Output is correct
53 Correct 3 ms 852 KB Output is correct
54 Correct 3 ms 852 KB Output is correct
55 Correct 3 ms 852 KB Output is correct
56 Correct 4 ms 852 KB Output is correct
57 Correct 3 ms 896 KB Output is correct
58 Correct 1 ms 596 KB Output is correct
59 Correct 5 ms 848 KB Output is correct
60 Correct 1 ms 724 KB Output is correct
61 Correct 861 ms 137640 KB Output is correct
62 Correct 1950 ms 281284 KB Output is correct
63 Correct 1945 ms 282820 KB Output is correct
64 Correct 1932 ms 282756 KB Output is correct
65 Correct 574 ms 139840 KB Output is correct
66 Correct 1179 ms 278932 KB Output is correct
67 Correct 1255 ms 282736 KB Output is correct
68 Correct 0 ms 340 KB Output is correct
69 Correct 1 ms 340 KB Output is correct
70 Correct 1 ms 1236 KB Output is correct
71 Correct 1 ms 1240 KB Output is correct
72 Correct 1 ms 596 KB Output is correct
73 Correct 2374 ms 317212 KB Output is correct
74 Correct 2374 ms 317212 KB Output is correct
75 Correct 2394 ms 317212 KB Output is correct
76 Correct 2347 ms 317232 KB Output is correct
77 Correct 2896 ms 315868 KB Output is correct
78 Correct 1676 ms 176204 KB Output is correct
79 Correct 1823 ms 258164 KB Output is correct
80 Correct 2804 ms 293280 KB Output is correct
81 Correct 1720 ms 191436 KB Output is correct
82 Correct 2331 ms 299044 KB Output is correct
83 Correct 2905 ms 318512 KB Output is correct
84 Correct 1646 ms 184084 KB Output is correct
85 Correct 2842 ms 318556 KB Output is correct
86 Correct 2835 ms 309912 KB Output is correct
87 Correct 1670 ms 260188 KB Output is correct
88 Correct 2850 ms 318252 KB Output is correct
89 Correct 2797 ms 318436 KB Output is correct
90 Correct 2826 ms 318420 KB Output is correct