Is this problem 1351C - Skier can be solved without stl(map/pair/set in cpp)? If it is then how?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

Is this problem 1351C - Skier can be solved without stl(map/pair/set in cpp)? If it is then how?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2020 22:48:34 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

A map makes it so easy, what would be the point of solving it without one?

I don't know how to implement map

so

The whole point of it being a standard template library is that you don't have to implement it yourself; you just need to learn how to use it.

I recommend investing a little bit of time to familiarize yourself with common tools that you are definitely going to need in order to be any good (such as maps/pairs/sets/vectors) before spending too much time worrying about which problems you can solve.

Yeah. Feel to implement red — black tree or treap

Being afraid of using any structures at all is a very bad plan that will hinder your progress. However, to answer your question:

yes it is possible to solve it without those things. You can make a list of all positions you visit during your ski trip. Each position has an x and y coordinate. You can store these into the first 32 bits and last 32 bits of a long long, so now you just have an array of long longs and you need to know how many unique numbers are in this array. If you sort the array with std::sort, then you can iterate through it and count how many times it changes. The first time you hit each new number (or equivalently, each new space) you have to pay 5 time units. Every future time you have to pay only 1 time unit.

Yea. You can struct your own data type and then solve it if you don't know how to use stl. If you wanna learn how to use stl, you can read this article(In Bangla). http://www.progkriya.org/gyan/stl.html