Submission #932306

#	Time	Username	Problem	Language	Result	Execution time	Memory
932306		salmon	Sky Walking (IOI19_walk)	C++14	Compilation error	0 ms	0 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

long long int inf = 1e18;

struct node{
    int s, e, m;
    int fleb;
    long long int v;
    node *l,*r;

    node(int S, int E, int fleba){
        s = S;
        e = E;
        fleb = fleba;
        m = (s + e)/2;

        v = inf;

        l = NULL;
        r = NULL;
    }

    void update(int i, long long int k){
        if(s == e){
            v = min(k + s * fleb,v);
            if(k == inf) v = inf;
            return;
        }

        if(l == NULL){
            l = new node(s,m,fleb);
            r = new node(m + 1,e,fleb);
        }

        if(i <= m){
            l -> update(i,k);
        }
        else{
            r -> update(i,k);
        }

        v = min(l -> v, r -> v);
    }

    long long int query(int S, int E){
        if(S <= s && e <= E){
            return v;
        }

        long long int V = inf;

        if(l == NULL) return inf;

        if(S <= m){
            V = min(V,l -> query(S,E));
        }
        if(m < S){
            V += min(V,r -> query(S,E));
        }

        return V;
    }
}*root,*froot;

vector<int> re[100100];
vector<int> er[100100];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {

    int N = x.size();

    int M = l.size();

    for(int i = 0; i < M; i++){
        re[l[i]].push_back(i);
        er[r[i]].push_back(i);
    }

    root = new node(0,1'000'000'000,1);
    froot = new node(0,1'000'000'000,-1);

    for(int j : re[0]){
        root -> update(y[j],y[j]);
        froot -> update(y[j],y[j]);
    }

    for(int i = 1; i < N; i++){
        set<int> oobless;
        set<int> ah;

        for(int j : re[i]){
            oobless.insert(j);
        }

        for(int j : er[i]){
            if(oobless.find(j) != oobless.end()){
                ah.insert(j);
            }
        }


        for(int j : re[i]){
            if(ah.find(j) != ah.end()) continue;

            long long int num = min(root -> query(y[j],1'000'000'000) - y[j], froot -> query(0,y[j]) + y[j]);
            if(num == inf) continue;
            root -> update(y[j],num);
            froot -> update(y[j],num);
        }


        if(i != N - 1){
            for(int j : er[i]){
                if(ah.find(j) != ah.end()) continue;

                root -> update(y[j],inf);
                froot -> update(y[j],inf);
            }
        }
    }


    if(root -> query(0,1'000'000'000) == inf) return -1;

	return root -> query(0,1'000'000'000) + x[N - 1] - x[0];
}

int main(){
    //printf("%d",min_distance({0, 4, 5, 6, 9},{6, 6, 6, 6, 6},{3, 1, 0},{4, 3, 2},{1, 3, 6},0, 4));
    printf("%d",min_distance({0, 3, 5, 7, 10, 12, 14},{8, 7, 9, 7, 6, 6, 9},{0, 0, 0, 2, 2, 3, 4},{1, 2, 6, 3, 6, 4, 6},{1, 6, 8, 1, 7, 2, 5},1, 5));

}

Compilation message (stderr)

walk.cpp: In function 'int main()':
walk.cpp:132:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  132 |     printf("%d",min_distance({0, 3, 5, 7, 10, 12, 14},{8, 7, 9, 7, 6, 6, 9},{0, 0, 0, 2, 2, 3, 4},{1, 2, 6, 3, 6, 4, 6},{1, 6, 8, 1, 7, 2, 5},1, 5));
      |             ~^  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |              |              |
      |              int            long long int
      |             %lld
/usr/bin/ld: /tmp/ccFlCaGh.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKt8Ytl.o:walk.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status