답안 #745705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745705	2023-05-21T03:07:13 Z	bgnbvnbv	Bob (COCI14_bob)	C++14	0 / 120	262 ms	65536 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]);
        //cout << l[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]-l[i]-1);
        //cout << l[i]<<' '<<r[i]<<'\n';
    }
    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]);
        }
    }
    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:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(i<cc.size()-1&&cc[i]==cc[i+1]-1)
      |            ~^~~~~~~~~~~~
bob.cpp: In function 'void solve()':
bob.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int v=0;v<val.size();v++)
      |                 ~^~~~~~~~~~~
bob.cpp:95: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]
   95 |         for(int i=0;i<vec[v].size();i++)
      |                     ~^~~~~~~~~~~~~~
bob.cpp:99: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]
   99 |             while(j<vec[v].size()&&vec[v][j].fi==vec[v][i].fi)
      |                   ~^~~~~~~~~~~~~~
bob.cpp:90:8: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   90 |     ll cur;
      |        ^~~

Subtask #1
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	12 ms	24404 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	24448 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	56 ms	36952 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	55 ms	38016 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	66 ms	37404 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	64 ms	37736 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	260 ms	65536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	262 ms	65536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	251 ms	65536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	254 ms	65536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-