Hi,
I am trying to do this problem. My solution is based off of the one in the editorial but mine has performance issues. Where is my code slowing down?
My code:
#include <bits/stdc++.h>
using namespace std;
int main(){
ifstream fin("snowboots.in");
int n,b,d,x,y;
fin>>n>>b;
vector<pair<int,int>> tiles(n); // snow, index
vector<pair<pair<int,int>,int>> boots(b); // resistance, step size, index
vector<int> dists(n-1); // Distances between ok tiles
fill(dists.begin(),dists.end(),1); // set beginning dists
int bv[b];
for(int i = 0; i<n; i++){
fin>>d;
tiles[i] = {d,i};
}
for(int j = 0; j<b; j++){
fin>>x>>y;
boots[j] = {{x,y},j};
}
sort(boots.rbegin(),boots.rend());
ofstream fout("snowboots.out");
for(auto b:boots){
for(unsigned k = 1; k<tiles.size()-1;){
if(tiles[k].first > b.first.first) { // if tile has too much snow
dists[k-1] += dists[k]; // move dist count to other element
dists.erase(dists.begin()+k); // delete this
tiles.erase(tiles.begin()+k); // remove this tile
}
else k++;
}
bv[b.second] = (b.first.second>=*max_element(dists.begin(),dists.end())); // if max dist is less than step size, FJ can pass
}
for(int v:bv) fout<<v<<'\n'; // output
}