| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 89363 |
2018-12-12T09:51:32 Z |
theknife2001 |
Bob (COCI14_bob) |
C++17 |
|
841 ms |
48692 KB |
#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define ii pair < int , int >
#define fi first
#define se second
using namespace std;
const int N=1055;
int a[N][N];
ii tree[N*4][N];
int lazy[N*4][N];
int n,m;
long long ans;
void propa(int l , int r , int node , int j)
{
if(lazy[node][j]==-1)
return ;
if(l!=r)
{
lazy[node*2][j]=lazy[node][j];
lazy[node*2+1][j]=lazy[node][j];
}
tree[node][j].fi=lazy[node][j]*(r-l+1);
tree[node][j].se=lazy[node][j];
lazy[node][j]=-1;
}
void update(int l , int r , int node , int x , int y , int val , int j)
{
propa(l,r,node,j);
if(x>r||l>y||x>y)
return ;
if(x<=l&&r<=y)
{
lazy[node][j]=val;
propa(l,r,node,j);
return ;
}
update(l,mid,node*2,x,y,val,j);
update(1+mid,r,1+node*2,x,y,val,j);
tree[node][j].fi=tree[node*2][j].fi+tree[node*2+1][j].fi;
tree[node][j].se=max(tree[node*2][j].se,tree[node*2+1][j].se);
}
int query(int l , int r , int node , int x , int y , int j)
{
propa(l,r,node,j);
if(x>r||l>y||x>y)
return 0;
if(x<=l&&r<=y)
return tree[node][j].fi;
return query(l,mid,node*2,x,y,j)+query(mid+1,r,node*2+1,x,y,j);
}
int sch(int l , int r , int node , int val , int j)
{
propa(l,r,node,j);
// cout<<l<<' '<<r<<' '<<val<<' '<<tree[node][j].se<<endl;
if(l==r)
return l;
propa(l,mid,node*2,j);
// cout<<l<<' '<<mid<<' '<<val<<' '<<tree[node*2][j].se<<endl;
if(tree[node*2][j].se>=val)
return sch(l,mid,node*2,val,j);
else
return sch(mid+1,r,node*2+1,val,j);
}
void bs(int i , int j , int c)
{
// cout<<i<<' '<<j<<endl;
int l=sch(0,n-1,1,c,j);
update(0,n-1,1,l,i,c,j);
ans+=query(0,n-1,1,0,i,j);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(lazy,-1,sizeof lazy);
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
int cnt=1;
for(int j=0;j<m;j++)
{
if(j)
{
if(a[i][j-1]==a[i][j])
cnt++;
else
cnt=1;
}
if(i)
{
if(a[i-1][j]!=a[i][j])
update(0,n-1,1,0,n-1,0,j);
update(0,n-1,1,i,i,cnt,j);
bs(i,j,cnt);
}
else
{
ans+=cnt;
update(0,n-1,1,i,i,cnt,j);
}
}
}
cout<<ans<<endl;
return 0;
}
/*
5 5
1 2 3 4 5
5 2 2 1 4
1 3 5 9 7
2 1 2 1 2
3 4 3 5 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
18424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
18560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
27792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
27900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
27920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
27940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
781 ms |
38804 KB |
Output is correct |
| 2 |
Correct |
745 ms |
38812 KB |
Output is correct |
| 3 |
Correct |
722 ms |
38816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
820 ms |
38868 KB |
Output is correct |
| 2 |
Correct |
761 ms |
38876 KB |
Output is correct |
| 3 |
Correct |
729 ms |
40688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
841 ms |
40728 KB |
Output is correct |
| 2 |
Correct |
741 ms |
42832 KB |
Output is correct |
| 3 |
Correct |
743 ms |
44600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
825 ms |
44720 KB |
Output is correct |
| 2 |
Correct |
830 ms |
46648 KB |
Output is correct |
| 3 |
Correct |
734 ms |
48692 KB |
Output is correct |
