// #include <bits/stdc++.h>
// #ifdef local
// #include "../../local.hpp"
// #else
// #define dbg(...)
// #endif
// using i64 = long long;
// #define int i64
// constexpr int MXN = 3E5 + 9;
// int n, m;
// int o[MXN] = {};
// int p[MXN] = {};
// int k;
// int l[MXN] = {};
// int r[MXN] = {};
// int a[MXN] = {};
// int lo[MXN] = {};
// int hi[MXN] = {};
// i64 t[MXN * 4] = {};
// void build(int v, int l, int r) {
// t[v] = 0;
// if (l == r) {
// t[v] = 0;
// return;
// }
// int mid = (l + r) / 2;
// build(v + v, l, mid);
// build(v + v + 1, mid + 1, r);
// }
// void upd(int v, int l, int r, int ql, int qr, i64 x) {
// if (ql <= l && r <= qr) {
// t[v] += x;
// return;
// }
// if (ql > r || qr < l) {
// return;
// }
// int mid = (l + r) / 2;
// upd(v + v, l, mid, ql, qr, x);
// upd(v + v + 1, mid + 1, r, ql, qr, x);
// }
// i64 get(int v, int l, int r, int pos, i64 sum) {
// sum += t[v];
// if (l == r) {
// return sum;
// }
// int mid = (l + r) / 2;
// if (pos <= mid) {
// return get(v + v, l, mid, pos, sum);
// } else {
// return get(v + v + 1, mid + 1, r, pos, sum);
// }
// }
// int32_t main() {
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr), std::cout.tie(nullptr);
// std::cin >> n >> m;
// for (int i = 1; i <= m; i++) {
// std::cin >> o[i];
// }
// for (int i = 1; i <= n; i++) {
// std::cin >> p[i];
// }
// std::cin >> k;
// for (int i = 1; i <= k; i++) {
// std::cin >> l[i] >> r[i] >> a[i];
// }
// for (int i = 0; i <= n; i++) {
// lo[i] = 1;
// hi[i] = k + 1;
// }
// std::map<int, std::vector<int>> ow;
// for (int i = 1; i <= m; i++) {
// ow[o[i]].push_back(i);
// }
// bool chk = true;
// std::map<int, std::set<int>> wrk;
// while (chk) {
// chk = false;
// build(1, 1, m);
// for (int i = 1; i <= n; i++) {
// if (lo[i] == hi[i]) {
// continue;
// }
// int m = (lo[i] + hi[i]) / 2;
// wrk[m].insert(i);
// }
// for (int q = 1; q <= k; q++) {
// if (l[q] <= r[q]) {
// upd(1, 1, m, l[q], r[q], a[q]);
// } else {
// upd(1, 1, m, 1, r[q], a[q]);
// upd(1, 1, m, l[q], m, a[q]);
// }
// for (auto x : wrk[q]) {
// chk = true;
// i64 su = 0;
// for (auto pls : ow[x]) {
// su += get(1, 1, m, pls, 0);
// if (su >= p[x]) {
// break;
// }
// }
// if (su >= p[x]) {
// hi[x] = q;
// } else {
// lo[x] = q + 1;
// }
// }
// }
// for (int i = 1; i <= k; i++) {
// wrk[i].clear();
// }
// }
// for (int i = 1; i <= n; i++) {
// if (lo[i] <= k) {
// std::cout << lo[i] << "\n";
// } else {
// std::cout << "NIE\n";
// }
// }
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 N = 3E3 + 5;
int z[N], x[N];
i64 b[N], c[N];
pair<int, int> lohi[N];
set<int> wrk[N];
vector<int> rg[N];
i64 t[4 * N];
void build(int v, int l, int r) {
t[v] = 0;
if (l == r) {
t[v] = 0;
return;
}
int mid = (l + r) / 2;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
}
void upd(int v, int l, int r, int ql, int qr, i64 x) {
if (ql <= l && r <= qr) {
t[v] += x;
return;
}
if (ql > r || qr < l)
return;
int mid = (l + r) / 2;
upd(v + v, l, mid, ql, qr, x);
upd(v + v + 1, mid + 1, r, ql, qr, x);
}
i64 get(int v, int l, int r, int pos, i64 sum) {
sum += t[v];
if (l == r)
return sum;
int mid = (l + r) / 2;
if (pos <= mid)
return get(v + v, l, mid, pos, sum);
else
return get(v + v + 1, mid + 1, r, pos, sum);
}
int32_t main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u;
cin >> u;
rg[u].push_back(i);
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> z[i] >> x[i] >> c[i];
}
for (int i = 1; i <= n; i++) {
lohi[i] = {1, q + 1};
}
bool chk = true;
while (chk) {
chk = false;
build(1, 1, m);
for (int i = 1; i <= n; i++) {
int md = (lohi[i].first + lohi[i].second) / 2;
wrk[md].insert(i);
}
for (int i = 1; i <= q; i++) {
if (z[i] <= x[i]) {
upd(1, 1, m, z[i], x[i], c[i]);
} else {
upd(1, 1, m, 1, x[i], c[i]);
upd(1, 1, m, z[i], m, c[i]);
}
for (int to : wrk[i]) {
chk = true;
i64 sum = 0;
for (int d : rg[to]) {
sum += get(1, 1, m, d, 0);
if (sum >= b[to]) {
break;
}
}
if (sum >= b[to]) {
lohi[to].second = i;
} else {
lohi[to].first = i + 1;
}
}
}
for (int i = 1; i <= q; i++) {
wrk[i].clear();
}
}
for (int i = 1; i <= n; i++) {
if (lohi[i].first <= q) {
std::cout << lohi[i].first << '\n';
} else {
std::cout << "NIE\n";
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6064 ms |
604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6063 ms |
604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
1628 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
5468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
5 ms |
5468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
7 ms |
1708 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
