This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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] ;
int 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()
{
char s[maxN][maxN] ;
int H , W , ans = 0 ;
scanf("%d%d",&H,&W) ;
for(int i = 0 ; i < H ; ++i)
{
scanf("%s",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("%d\n",ans) ;
return 0 ;
}
Compilation message (stderr)
joi2019_ho_t1.cpp: In function 'int main()':
joi2019_ho_t1.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
33 | scanf("%d%d",&H,&W) ;
| ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t1.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
36 | scanf("%s",s[i]) ;
| ~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |