# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
704765 |
2023-03-03T01:22:08 Z |
dubabuba |
Toll (BOI17_toll) |
C++14 |
|
3000 ms |
22628 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 3e5 + 10;
map<pii, int> mp;
int n, m, k, q;
bool inmap(pii p) {
auto it = mp.find(p);
return it != mp.end();
}
void pushmap(pii p, int val) {
if(inmap(p)) return;
mp[p] = val;
}
void build(int l, int r) {
cout << "building: " << l << ' ' << r << '\n';
if(r - l < 2) return;
int m = (l + r) / 2;
build(l, m);
build(m, r);
for(int L = 1; L <= k; L++)
for(int R = 1; R <= k; R++)
for(int M = 1; M <= k; M++) {
int st = L + (l - 1) * k;
int en = R + (r - 1) * k;
int md = M + (m - 1) * k;
// if(en > n) break;
if(inmap(MP(st, md)) && inmap(MP(md, en))) {
int sus = mp[MP(st, en)];
int LL = mp[MP(st, md)];
int RR = mp[MP(md, en)];
if(sus == 0) mp[MP(st, en)] = LL + RR;
else if(sus > LL + RR)
mp[MP(st, en)] = LL + RR;
cout << "l = " << l << ' ' << k << ' ' << L << ' ' << st << '\n';
cout << "r = " << r << ' ' << k << ' ' << R << ' ' << en << '\n';
cout << " " << mp[MP(st, en)] << '\n';
}
}
}
int query(int l, int r) {
int L = 1, R = n / k + 1;
while(R - L > 1) {
int M = (L + R) / 2, ret = INT_MAX;
bool sus = 0;
for(int t = 1; t <= k; t++) {
int mid = t + (M - 1) * k;
if(l <= mid && mid <= r) {
sus = 1;
if(inmap(MP(l, mid)) && inmap(MP(mid, r)))
ret = min(ret, mp[MP(l, mid)] + mp[MP(mid, r)]);
}
}
if(sus) return (ret == INT_MAX) ? -1 : ret;
if(M * k - 1 < l) L = M;
if(r < M * (k - 1) + 1) R = M;
}
return -1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n >> m >> q;
for(int i = 0; i < m; i++) {
int s, f, t;
cin >> s >> f >> t;
mp[MP(s + 1, f + 1)] = t;
}
build(1, n / k + 1);
while(q--) {
int l, r;
cin >> l >> r;
l++, r++;
if(inmap(MP(l, r)))
cout << mp[MP(l, r)] << '\n';
else
cout << query(l, r) << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3055 ms |
11116 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3072 ms |
22628 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3055 ms |
11116 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |