oj.uz

Submission #335712

# Submission time Handle Problem Language Result Execution time Memory
335712 2020-12-13T18:30:48 Z shahriarkhan Bitaro the Brave (JOI19_ho_t1) C++14
20 / 100
 18 ms 3940 KB 
#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

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]) ;
      |         ~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 748 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 748 KB Output is correct
14 Correct 14 ms 3300 KB Output is correct
15 Correct 2 ms 1772 KB Output is correct
16 Correct 6 ms 2152 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 18 ms 3940 KB Output is correct
19 Correct 9 ms 3324 KB Output is correct
20 Incorrect 9 ms 3320 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 748 KB Output is correct
14 Correct 14 ms 3300 KB Output is correct
15 Correct 2 ms 1772 KB Output is correct
16 Correct 6 ms 2152 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 18 ms 3940 KB Output is correct
19 Correct 9 ms 3324 KB Output is correct
20 Incorrect 9 ms 3320 KB Output isn't correct
21 Halted 0 ms 0 KB -