Submission #1288428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288428		vincentbucourt1	Shortcut (IOI16_shortcut)	C++20	Compilation error	0 ms	0 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!
#pragma "O3"

const ll OO = (ll)1e14;

template<ll (*op)(ll&, ll&), ll NULLVAL>
struct Fenwick {
    int N;
    vector<int> tree;
    void reset (int n) {
        N = n;
        tree.assign(N+1, NULLVAL);
    }
    int query (int idx) {
        ll res = NULLVAL;
        idx++;
        while (idx > 0) {
            res = op(res, tree[idx]);
            idx -= idx&(-idx);
        }
        return res;
    }
    void update (int idx, ll val) {
        idx++;
        while (idx <= N) {
            tree[idx] = op(tree[idx], val);
            idx += idx&(-idx);
        }
    }
};
ll maxi (ll& a, ll& b) {return max(a, b);}
ll mini (ll& a, ll& b) {return min(a, b);}

vector<int> incR, decL;
Fenwick<maxi, -OO> xMinQ;
Fenwick<mini, OO> xMaxQ;
Fenwick<maxi, -OO> yMinQ;
Fenwick<mini, OO> yMaxQ;

bool test (ll UB, int& N, vector<ll>& dist, vector<int>& lenDown, const int& costBridge) {
    // x = r-l, y = r+l
    xMinQ.reset(N);
    xMaxQ.reset(N);
    yMinQ.reset(N);
    yMaxQ.reset(N);
    ll xMin = -OO, xMax = OO, yMin = -OO, yMax = OO;
    int iDecL = 0;
    for (int iIncR = 0; iIncR < N; iIncR++) {
        int iR = incR[iIncR];
        while (iDecL < N && (-dist[decL[iDecL]] + lenDown[decL[iDecL]]) > UB - (dist[iR] + lenDown[iR])) {
            int iL = decL[iDecL];
            xMinQ.update(iL, -dist[iL] + lenDown[iL]);
            xMaxQ.update(iL, -dist[iL] - lenDown[iL]);
            yMinQ.update(iL, dist[iL] + lenDown[iL]);
            yMaxQ.update(iL, dist[iL] - lenDown[iL]);
            iDecL++;
        }
        xMin = max(xMin, dist[iR] + lenDown[iR] - UB + costBridge + xMinQ.query(iR-1));
        xMax = min(xMax, dist[iR] - lenDown[iR] + UB - costBridge + xMaxQ.query(iR-1));
        yMin = max(yMin, dist[iR] + lenDown[iR] - UB + costBridge + yMinQ.query(iR-1));
        yMax = min(yMax, dist[iR] - lenDown[iR] + UB - costBridge + yMaxQ.query(iR-1));
    }
    // cerr << "UB: " << UB << ", " << xMin << " " << xMax << ", " << yMin << " " << yMax << "\n";
    for (int iL = 0; iL < N-1; iL++) {
        int iR = lower_bound(dist.begin(), dist.end(), max(xMin + dist[iL], yMin - dist[iL])) - dist.begin();
        if (iR < N && dist[iR] <= min(xMax + dist[iL], yMax - dist[iL])) {
            return true;
        }
    }
    return false;
}

ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
    vector<ll> dist(N, 0);
    for (int i = 0; i < N-1; i++) {
        dist[i+1] = dist[i] + lenSide[i];
        assert(dist[i] < dist[i+1]);
    }
    incR.assign(N, 0);
    iota(incR.begin(), incR.end(), 0);
    sort(incR.begin(), incR.end(), [&](const int& a, const int& b)->bool{
        return (dist[a] + lenDown[a] < dist[b] + lenDown[b]);
    });
    decL.assign(N, 0);
    iota(decL.begin(), decL.end(), 0);
    sort(decL.begin(), decL.end(), [&](const int& a, const int& b)->bool{
        return (-dist[a] + lenDown[a] > -dist[b] + lenDown[b]);
    });
    ll loBS = 0, hiBS = OO;
    while (loBS < hiBS-1) {
        ll midBS = loBS + (hiBS - loBS) / 2;
        assert(loBS <= midBS && midBS <= hiBS);
        if (test(midBS, N, dist, lenDown, costBridge)) {
            hiBS = midBS;
        }
        else {
            loBS = midBS;
        }
    }
    return hiBS;
}

Compilation message (stderr)

shortcut.cpp: In member function 'int Fenwick<op, NULLVAL>::query(int)':
shortcut.cpp:21:21: error: cannot bind non-const lvalue reference of type 'long long int&' to a value of type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
   21 |             res = op(res, tree[idx]);
      |                   ~~^~~~~~~~~~~~~~~~
shortcut.cpp: In member function 'void Fenwick<op, NULLVAL>::update(int, long long int)':
shortcut.cpp:29:27: error: cannot bind non-const lvalue reference of type 'long long int&' to a value of type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
   29 |             tree[idx] = op(tree[idx], val);
      |                         ~~^~~~~~~~~~~~~~~~
shortcut.cpp: In instantiation of 'void Fenwick<op, NULLVAL>::reset(int) [with long long int (* op)(long long int&, long long int&) = maxi; long long int NULLVAL = -100000000000000]':
shortcut.cpp:45:16:   required from here
shortcut.cpp:15:20: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-100000000000000' to '-276447232' [-Woverflow]
   15 |         tree.assign(N+1, NULLVAL);
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~
shortcut.cpp: In instantiation of 'void Fenwick<op, NULLVAL>::reset(int) [with long long int (* op)(long long int&, long long int&) = mini; long long int NULLVAL = 100000000000000]':
shortcut.cpp:46:16:   required from here
shortcut.cpp:15:20: warning: overflow in conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '100000000000000' to '276447232' [-Woverflow]
shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~