Submission #745707

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745707	2023-05-21T03:17:40 Z	bgnbvnbv	Bob (COCI14_bob)	C++14	120 / 120	298 ms	63408 KB

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
vector<int> cc;
deque<int> dq;
ll h[1005][1005];
ll l[1005],r[1005];
ll n,m;
ll process(ll x)
{
    dq.clear();
    dq.pb(0);
    for(int i=0;i<cc.size();i++)
    {
        if(i>0&&cc[i]==cc[i-1]+1)
        {
            while(dq.size()>0&&h[x][cc[i]]<h[x][dq.back()])
            {
                dq.pop_back();
            }
            if(dq.size()==0) l[i]=0;
            else l[i]=dq.back();
        }
        else
        {
            dq.clear();
            dq.pb(cc[i]-1);
            l[i]=cc[i]-1;
        }
        dq.pb(cc[i]);
    }
    dq.clear();
    dq.pb(m+1);
    ll sum=0;
    for(int i=(int)cc.size()-1;i>=0;i--)
    {
        if(i<cc.size()-1&&cc[i]==cc[i+1]-1)
        {
            while(dq.size()>0&&h[x][cc[i]]<=h[x][dq.back()]) dq.pop_back();
            if(dq.size()==0) r[i]=m+1;
            else r[i]=dq.back();
        }
        else
        {
            dq.clear();
            dq.pb(cc[i]+1);
            r[i]=dq.back();
        }
        dq.pb(cc[i]);
        sum+=h[x][cc[i]]*(r[i]-cc[i])*(cc[i]-l[i]);
    }
    return sum;

}
ll a[1005][1005];
vector<ll>val;
vector<pli>vec[1005*1000];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> a[i][j];
            val.pb(a[i][j]);
            h[i][j]=0;
        }
    }
    sort(val.begin(),val.end());
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=lower_bound(val.begin(),val.end(),a[i][j])-val.begin();
            vec[a[i][j]].pb({i,j});
        }
    }
    ll ans=0;
    ll cur;
    for(int v=0;v<val.size();v++)
    {
        if(vec[v].size()==0) continue;
        cur=ans;
        for(int i=0;i<vec[v].size();i++)
        {
            cc.clear();
            ll j=i;
            while(j<vec[v].size()&&vec[v][j].fi==vec[v][i].fi)
            {
                ll x=vec[v][j].fi;
                ll y=vec[v][j].se;
                h[x][y]=h[x-1][y]+1;
                cc.pb(y);
                j++;
            }
            i=j-1;
            ans+=process(vec[v][i].fi);
        }
        for(auto zz:vec[v])
        {
            h[zz.fi][zz.se]=0;
        }
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

bob.cpp: In function 'll process(ll)':
bob.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<cc.size();i++)
      |                 ~^~~~~~~~~~
bob.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(i<cc.size()-1&&cc[i]==cc[i+1]-1)
      |            ~^~~~~~~~~~~~
bob.cpp: In function 'void solve()':
bob.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int v=0;v<val.size();v++)
      |                 ~^~~~~~~~~~~
bob.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i=0;i<vec[v].size();i++)
      |                     ~^~~~~~~~~~~~~~
bob.cpp:98:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while(j<vec[v].size()&&vec[v][j].fi==vec[v][i].fi)
      |                   ~^~~~~~~~~~~~~~
bob.cpp:89:8: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   89 |     ll cur;
      |        ^~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	24404 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	24452 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	36612 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	37412 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	36408 KB	Output is correct

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	36864 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	276 ms	60864 KB	Output is correct
2	Correct	139 ms	61648 KB	Output is correct
3	Correct	135 ms	61652 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	242 ms	61608 KB	Output is correct
2	Correct	149 ms	63408 KB	Output is correct
3	Correct	131 ms	61740 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	273 ms	61916 KB	Output is correct
2	Correct	142 ms	61788 KB	Output is correct
3	Correct	147 ms	61716 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	61652 KB	Output is correct
2	Correct	143 ms	61748 KB	Output is correct
3	Correct	145 ms	61624 KB	Output is correct