Submission #745706

#	Time	Username	Problem	Language	Result	Execution time	Memory
745706		bgnbvnbv	Bob (COCI14_bob)	C++14	0 / 120	19 ms	24008 KiB

bob

#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 (stderr)

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;
      |        ^~~
bob.cpp: In function 'int main()':
bob.cpp:119:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     freopen(TASKNAME".INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12