| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 660847 | rukashii | Meteors (POI11_met) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 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;
if (!opt[mid].size())
continue;
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 < min(mid, query.size()); 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 < min(q, query.size()); 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';
}