Submission #1113955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113955		lucascgar	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	2385 ms	3288 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

/*
se eu tenho um cara da esquerda sempre vale pegar primeiro cara que der da direita
se eu tenho um destino na direita sempre vale pegar o maior cara da esquerda q chega la
nenhuma subtituição nos intervalos muda nada pq 
*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 2e5+10, MAXQ = 1e5+10, BIG = 1e9+8;

int n, h[MAXN], ds[MAXN];
bool thing = 0;
void init(int N, vector<int> H){
    n = N;
    thing = 1;
    for (int i=0;i<n;i++){
        h[i] = H[i];
        if (h[i]!=i+1) thing=0;
    }


}
int minimum_jumps(int A, int B, int C, int D){  // A <= B < C <= D
    if (thing){
        return C-B;
    }
    vector<int> ps(n+1, 0);
    for (int i=A;i<=D;i++) ps[h[i]]++;
    for (int i=1;i<=n;i++) ps[i] += ps[i-1];

    vector<int> lf, rg;
    for (int i=A;i<=B;i++) lf.push_back(h[i]);
    for (int i=C;i<=D;i++) rg.push_back(h[i]);

    sort(lf.begin(), lf.end());
    sort(rg.begin(), rg.end());

    int i=0, ans = BIG;

    for (int j=0;j<rg.size();j++){
        while (i+1<lf.size() && lf[i+1]<rg[j]) i++;
        if (lf[i]<rg[j]){
            int cst = ps[rg[j]-1]-ps[lf[i]]+1;
            if (cst<ans) ans = cst;
        }
    }


    if (ans==BIG) return -1;
    return ans;

}

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int j=0;j<rg.size();j++){
      |                  ~^~~~~~~~~~
jumps.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while (i+1<lf.size() && lf[i+1]<rg[j]) i++;
      |                ~~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19