Submission #569354

#	Time	Username	Problem	Language	Result	Execution time	Memory
569354		BadPenalty	Rainforest Jumps (APIO21_jumps)	C++14	Compilation error	0 ms	0 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
const int N = 1e6,mod = 1e9+7;
vector<int>A;
vector<int>adj[N];
int n,dst[N];
bool vstd[N];
void init(int N, std::vector<int> H)
{
    n = N;
    A = H;
    set<int>s;
    s.insert(A[0]);
    for(int i = 1;i<n;i++)
    {
        while(!s.empty()&&*s.begin()<A[i])
            s.erase(s.begin());
        if(!s.empty())
            adj[A[i]].pb(*s.begin());
        s.insert(A[i]);
    }
    s.clear();
    s.insert(A[n-1]);
    for(int i = n-2;i>=0;i--)
    {
        while(!s.empty()&&*s.begin()<A[i])
            s.erase(s.begin());
        if(!s.empty())
            adj[A[i]].pb(*s.begin());
        s.insert(A[i]);
    }

    return;
}

int minimum_jumps(int a, int B, int C, int D)
{
    for(int i = 0;i<n;i++)
        vstd[i] = 0,dst[A[i]] = 1e9;
    queue<int>q;
    for(int i = a;i<=B;i++)
    {
        q.push(A[i]);
        dst[A[i]] = 0;
    }
    while(!q.empty())
    {
        int nd = q.front();
        q.pop();
        if(vstd[nd])continue;
        vstd[nd] = 1;

        for(auto u:adj[nd])
        {
            if(dst[u]>dst[nd]+1)
            {
                dst[u] = dst[nd]+1;
                q.push(u);
            }
        }
    }
    int ans = 1e9;
    for(int i = C;i<=D;i++)
    {
        ans = min(ans,dst[A[i]]);
    }
    return ans;
}

int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccrEDhZi.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccir1Vbk.o:jumps.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status