Submission #335709

#	Time	Username	Problem	Language	Result	Execution time	Memory
335709		shahriarkhan	Bitaro the Brave (JOI19_ho_t1)	C++14	50 / 100	1016 ms	81552 KiB

joi2019_ho_t1

#include<bits/stdc++.h>
using namespace std ;

//type 0 -> orb
//type 1 -> ingot

const int maxN = 3e3 + 5 ;

int SIZ[maxN][2] ;

vector<pair<int,int> > jewels ;

vector<int> mine[maxN][2] ;

long long bs(int low , int high , int type , int val , int par)
{
    if(high<low) return 0 ;
    int N = high + 1 ;
    while(low<high)
    {
        int mid = (low+high)/2 ;
        if(mine[par][type][mid]>val) high = mid ;
        else low = mid + 1 ;
    }
    if(mine[par][type][low]<=val) return 0 ;
    else return N - low ;
}

int main()
{
    long long ans = 0 ;
    string s[maxN] ;
    int H , W ;
    scanf("%d%d",&H,&W) ;
    for(int i = 0 ; i < H ; ++i)
    {
        cin>>s[i] ;
    }
    for(int i = 0 ; i < H ; ++i)
    {
        for(int j = 0 ; j < W ; ++j)
        {
            if(s[i][j]=='J') jewels.push_back({i,j}) ;
            else if(s[i][j]=='O') mine[i][0].push_back(j) ;
            else mine[j][1].push_back(i) ;
        }
    }
    for(int i = 0 ; i < maxN ; ++i)
    {
        if(!mine[i][0].empty())
        {
            sort(mine[i][0].begin(),mine[i][0].end()) ;
            SIZ[i][0] = mine[i][0].size() ;
        }
        if(!mine[i][1].empty())
        {
            sort(mine[i][1].begin(),mine[i][1].end()) ;
            SIZ[i][1] = mine[i][1].size() ;
        }
    }
    for(pair<int,int> p : jewels)
    {
        int i = p.first , j = p.second ;
        ans += (bs(0,SIZ[i][0]-1,0,j,i)*bs(0,SIZ[j][1]-1,1,i,j)) ;
    }
    printf("%lld\n",ans) ;
    return 0 ;
}

Compilation message (stderr)

joi2019_ho_t1.cpp: In function 'int main()':
joi2019_ho_t1.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%d%d",&H,&W) ;
      |     ~~~~~^~~~~~~~~~~~~~

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