#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 6e5 + 2;
int n, m, a[maxn], q, tree[maxn], ans[maxn], bad[maxn];
vector <pair <int, pair <int, int>>> query;
vector <int> st[maxn], opt[maxn];
void update(int pos, int val)
{
for (int i = pos; i <= m; i += (i & (-i)))
{
tree[i] += val;
}
}
int get(int pos)
{
int ret = 0;
for (int i = pos; i >= 1; i -= (i & (-i)))
{
ret += tree[i];
}
return ret;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
memset(ans, -1, sizeof(ans));
memset(bad, -1, sizeof(bad));
//freopen("input.inp", "r", stdin);
//freopen("output.out", "w", stdout);
cin >> n >> m;
for (int i = 1, t; i <= m; i++)
{
cin >> t;
st[t].push_back(i);
}
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> q;
for (int i = 1; i <= q; i++)
{
int l, r, w;
cin >> l >> r >> w;
query.push_back({l, {r, w}});
}
for (int i = 1; i <= n; i++)
opt[(1 + q) / 2].push_back(i);
queue <pair <int, int>> qe;
qe.push({1, q});
while (qe.size())
{
auto [l, r] = qe.front();
qe.pop();
memset(tree, 0, sizeof(tree));
if (l >= r)
continue;
int mid = (l + r) / 2;
int l_mid = (l + mid) / 2;
int r_mid = (mid + 1 + r) / 2;
qe.push({l, mid});
qe.push({mid + 1, r});
for (int i = 0; i < mid; i++)
{
int u = query[i].first;
pair <int, int> tam = query[i].second;
int v = tam.first, f = tam.second;
if (u <= v)
{
update(u, f);
update(v + 1, -f);
}
else
{
update(1, f);
update(v + 1, -f);
update(u, f);
}
}
for (int p : opt[mid])
{
bool skip = 0;
int sum = 0;
for (int child : st[p])
{
sum += get(child);
}
if (sum < a[p])
{
opt[r_mid].push_back(p);
if (bad[p] == -1)
bad[p] = 1;
}
else
opt[l_mid].push_back(p), ans[p] = mid, bad[p] = 0;
}
opt[mid].clear();
}
memset(tree, 0, sizeof(tree));
for (int i = 0; i < q; i++)
{
int u = query[i].first;
pair <int, int> tam = query[i].second;
int v = tam.first, f = tam.second;
if (u <= v)
{
update(u, f);
update(v + 1, -f);
}
else
{
update(1, f);
update(v + 1, -f);
update(u, f);
}
}
for (int i = 1; i < q; i++)
{
for (int tmp : opt[i])
{
if (!bad[tmp])
ans[tmp] = i;
}
}
for (int tmp : opt[q])
{
int sum = 0;
for (int child : st[tmp])
{
sum += get(child);
}
if (sum >= a[tmp])
ans[tmp] = q;
}
for (int i = 1; i <= n; i++)
if (ans[i] == -1)
cout << "NIE\n";
else
cout << ans[i] << '\n';
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:108:9: warning: unused variable 'skip' [-Wunused-variable]
108 | bool skip = 0;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
130 ms |
65536 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
255 ms |
42824 KB |
Output is correct |
| 2 |
Correct |
287 ms |
42704 KB |
Output is correct |
| 3 |
Runtime error |
121 ms |
65536 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6054 ms |
46012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6063 ms |
47248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6075 ms |
46232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6034 ms |
45280 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6057 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
6083 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
