Submission #936573

#	Time	Username	Problem	Language	Result	Execution time	Memory
936573		adkjt	Bitaro the Brave (JOI19_ho_t1)	C++14	0 / 100	12 ms	26972 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
using namespace std;
/*struct O
{
    int l,i;
    bool operator<(const O&o)const{
        return l<o.l;
    }
};
struct I
{
    int k,j;
    bool operator<(const I&o)const{
        return k<o.k;
    }
};*/
char t[3333][3333];
vector<pair<int,int>> vo;
vector<pair<int,int>> vi;
int qsi[3333][3333];
int qsj[3333][3333];
queue<pair<int,int>> J;
int main()
{
    cin.tie()->sync_with_stdio(0);
    int r,c;cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
    {
        cin>>t[i][j];
        if(t[i][j]=='J')
        J.push({i,j});
        else if(t[i][j]=='O')
            vo.push_back({j,i});
        else
            vi.push_back({i,j});
    }
    long long ans=0;
    sort(vo.begin(),vo.end());
    sort(vi.begin(),vi.end());
   /* for(int i=0;i<vo.size();i++)
        cout<<vo[i].i<<' '<<vo[i].l<<'\n';*/
    for(int i=1;i<=vi.size();i++)
    {
        for(int j=1;j<=3000;j++)
        {
            qsj[j][i]=qsj[j][i-1]+(vi[i-1].second==j);
        }
    }
    for(int i=1;i<=vo.size();i++)
    {
        for(int j=1;j<=3000;j++)
        {
            qsi[j][i]=qsi[j][i-1]+(vo[i-1].second==j);
        }
    }
    /*for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=6;j++)
            cout<<qsj[i][j]<<' ';
        cout<<'\n';
    }
    cout<<'\n';
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=6;j++)
            cout<<qsi[i][j]<<' ';
        cout<<'\n';
    }*/
    while(!J.empty())
    {
        pair<int,int> now=J.front();
       // cout<<now.first<<' '<<now.second<<'\n';
        J.pop();
        //int id1,id2;
        /*O to={now.second,0};
        I ti={now.first,0};*/
        auto id1=upper_bound(vo.begin(),vo.end(),make_pair(now.first,0))-vo.begin();
        auto id2=upper_bound(vi.begin(),vi.end(),make_pair(now.second,0))-vi.begin();
        /*cout<<id1<<' '<<id2<<'\n';
        cout<<qsi[now.first][vo.size()]<<' '<<qsi[now.first][id1]<<' '<<qsj[now.second][vi.size()]<<' '<<qsj[now.second][id2]<<'\n';*/
        ans+=(qsi[now.first][id1]-qsi[now.first][vo.size()])*(qsj[now.second][id2]-qsj[now.second][vi.size()]);
    }

    cout<<ans;
}

Compilation message (stderr)

joi2019_ho_t1.cpp: In function 'int main()':
joi2019_ho_t1.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=1;i<=vi.size();i++)
      |                 ~^~~~~~~~~~~
joi2019_ho_t1.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=1;i<=vo.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50