Submission #1191401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191401		MateiKing80	Toll (BOI17_toll)	C++17	100 / 100	172 ms	20296 KiB

toll

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll
const int inf = 1e10 + 1e5;
int K;

struct spm
{
    vector<vector<int>> M;

    spm(int dim, int initVal, int diagVal)
    {
        M = vector<vector<int>> (dim, vector<int> (dim, initVal));
        for(int i = 0; i < dim; i ++)
            M[i][i] = diagVal;
    }

    inline int dim()
    {
        return M.size();
    }
};

spm operator + (spm L, spm R)
{
    int dim = L.dim();
    spm ans(dim, 0, 0);
    for(int i = 0; i < dim; i ++)
    {
        for(int j = 0; j < dim; j ++)
        {
            int cur = L.M[i][0] + R.M[0][j];
            for(int k = 1; k < dim; k ++)
            {
                int newVal = L.M[i][k] + R.M[k][j];
                cur = cur < newVal ? cur : newVal;
            }
            ans.M[i][j] = cur;
        }
    }
    return ans;
}

struct bst
{
    vector<spm> a;
    int N;
    int offs;

    bst(vector<spm> initArray)
    {
        int n = initArray.size();
        N = 2;
        while (N < 2 * n + 4)
            N *= 2;
        offs = N / 2 + 1;
        a = vector<spm> (N, spm(K, inf, inf));
        for(int i = 0; i < n; i ++)
            a[i + offs] = initArray[i];
        for(int i = offs - 2; i > 0; i --)
            a[i] = a[2 * i] + a[2 * i + 1];
    }

    spm sum(int i, int j)
    {
        int L = i + offs - 1;
        int R = j + offs + 1;
        spm Lans(K, inf, (int)0);
        spm Rans(K, inf, (int)0);
        while (true)
        {
            bool Lright = L % 2 == 0;
            bool Rleft = R % 2 == 1;
            L /= 2;
            R /= 2;
            if (L == R)
                break;
            if (Lright)
                    Lans = Lans + a[2 * L + 1];
            if (Rleft)
                Rans = a[2 * R] + Rans;
        }
        return Lans + Rans;
    }
};

signed main()
{
    int N, M, O;
    cin >> K >> N >> M >> O;
    vector<spm> initArray(N / K, spm(K, inf, inf));
    for (int i = 0; i < M; i ++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        initArray[a / K].M[a % K][b % K] = t;
    }
    bst T(initArray);
    for (int i = 0; i < O; i ++)
    {
        int a, b;
        cin >> a >> b;
        if(a / K >= b / K)
            cout << "-1\n";
        else
        {
            spm ans = T.sum(a / K, b / K - 1);
            cout << (ans.M[a % K][b % K] < inf ? ans.M[a % K][b % K] : -1) << '\n';
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44