제출 #1191401

#제출 시각아이디문제언어결과실행 시간메모리
1191401MateiKing80Toll (BOI17_toll)C++17
100 / 100
172 ms20296 KiB
#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'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...