Submission #1063478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063478		RaresFelix	Dungeons Game (IOI21_dungeons)	C++17	Compilation error	0 ms	0 KiB

dungeons

#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;
using pl = pair<ll, ll>;

const ll INF2 = 1e18;
const int INF = 1e9;

struct AINT {
    int n;
    vll Mi, Ma, Lz;
    AINT(int N) : n(N), Mi(4 * N, 0), Ma(4 * N, 0), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        if(!Lz[u]) return;
        Mi[u] += Lz[u];
        Ma[u] += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int l, int r, ll v, int u, int s, int d) {
        prop(u, s, d);
        if(d < l || r < s) return;
        if(l <= s && d  <= r) {
            Lz[u] += v;
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
        Ma[u] = max(Ma[u << 1], Ma[u << 1 | 1]);
    }

    void update(int l, int r, ll v) { update(l, r, v, 1, 0, n - 1); }

    bool query(int c, ll &mi, ll &ma, pl &prev, int u, int s, int d) {
        prop(u, s, d);
        if(max(Ma[u], ma) - min(Mi[u], mi) <= c) {
            mi = min(mi, Mi[u]);
            ma = max(ma, Ma[u]);
            return false;
        }
        if(s == d) {
            prev = {Mi[u], Ma[u]};
            return true;
        }
        if(!query(c, mi, ma, prev, u << 1 | 1, ((s + d) >> 1) + 1, d))
            query(c, mi, ma, prev, u << 1, s, (s + d) >> 1);
        return true;
    }

    void afis(int u, int s, int d) {
        prop(u, s, d);
        if(s == d) {
            cout << Mi[u] << " ";
            return;
        }
        afis(u << 1, s, (s + d) >> 1);
        afis(u << 1 | 1, ((s + d) >> 1) + 1, d);
    }

    void afis(string s = "") {
        cout << s;
        afis(1, 0, n - 1);
        cout << "\n";
    }

    void query(int c, ll &mi, ll &ma, pl &prev) {
        mi = INF2;
        ma = -INF2;
        query(c, mi, ma, prev, 1, 0, n - 1);
    }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = int(c.size()), m = int(l.size());
    vector<vector<ii> > Op(n);
    ///o operatie e (poz, val)
    Op[0].push_back({0, INF});
    Op[0].push_back({1, -INF});
    for(int i = 0; i < m; ++i) {
        Op[l[i]].push_back({i + 2, v[i]});
        if(r[i] + 1 < n) 
            Op[r[i] + 1].push_back({i + 2, -v[i]});
    }
    AINT Sol(m + 2);
    vi Re(n, 0);
    ll s = 0;
    for(int i = 0; i < n; ++i) {
        for(auto [p, v] : Op[i]) {
            Sol.update(p, m + 1, v);
            s += v;
        }
        ll mi, ma;
        pl prev;
        Sol.query(c[i], mi, ma, prev);
       // Sol.afis("Sol la " + to_string(i) + " = ");
        if(prev.second > ma) {
            //a murit la mi
            Re[i] = s - mi;
        } else {
            Re[i] = s - (ma - c[i]);
        }
    }
    return Re;
}

Compilation message (stderr)

dungeons.cpp:1:10: fatal error: candies.h: No such file or directory
    1 | #include "candies.h"
      |          ^~~~~~~~~~~
compilation terminated.