#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=3e5+5;
int n, m, p[nx], q, l[nx], r[nx], ul, ur, a, cnt=19, t[nx];
vector<int> d[nx], qrs[nx];
vector<pair<int, pair<int, int>>> k;
struct fenwick
{
ll d[nx];
void update(int i, int vl)
{
while (i<nx) d[i]+=vl, i+=(i&-i);
}
ll query(int i)
{
ll res=0;
while (i>0) res+=d[i], i-=(i&-i);
return res;
}
} f;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>p[i], d[p[i]].push_back(i);
for (int i=1; i<=n; i++) cin>>t[i];
cin>>q;
for (int i=0; i<q; i++) cin>>ul>>ur>>a, k.push_back({a, {ul, ur}});
for (int i=1; i<=n; i++) l[i]=1, r[i]=q+1;
while (cnt--)
{
for (int i=1; i<=n; i++) if (l[i]!=r[i]) qrs[(l[i]+r[i])/2].push_back(i);
for (int i=1; i<=q+1; i++)
{
if (i==q+1) continue;
int x=k[i-1].second.first, y=k[i-1].second.second, z=k[i-1].first;
if (x<=y) f.update(x, z), f.update(y+1, -z);
else f.update(1, z), f.update(y+1, -z), f.update(x, z), f.update(m+1, -z);
//cout<<"fenwick "<<i<<':';
//for (int j=1; j<=m; j++) cout<<f.query(j)<<' ';
//cout<<'\n';
for (auto idx:qrs[i])
{
ll sm=0;
for (auto id:d[idx]) sm+=f.query(id);
//cout<<"debug "<<cnt<<' '<<idx<<' '<<sm<<'\n';
if (sm>=t[idx]) r[idx]=i;
else l[idx]=i+1;
}
qrs[i].clear();
}
for (int i=1; i<=m+1; i++) f.d[i]=0;
}
for (int i=1; i<=n; i++)
{
if (l[i]>q) cout<<"NIE\n";
else cout<<l[i]<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
20828 KB |
Output is correct |
2 |
Correct |
6 ms |
20828 KB |
Output is correct |
3 |
Correct |
8 ms |
20828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
20828 KB |
Output is correct |
2 |
Correct |
7 ms |
20828 KB |
Output is correct |
3 |
Correct |
7 ms |
21080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
66 ms |
22488 KB |
Output is correct |
2 |
Correct |
137 ms |
24132 KB |
Output is correct |
3 |
Correct |
91 ms |
24012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
113 ms |
23624 KB |
Output is correct |
2 |
Correct |
111 ms |
23496 KB |
Output is correct |
3 |
Correct |
129 ms |
24208 KB |
Output is correct |
4 |
Correct |
27 ms |
22564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
22728 KB |
Output is correct |
2 |
Correct |
117 ms |
24780 KB |
Output is correct |
3 |
Correct |
132 ms |
21712 KB |
Output is correct |
4 |
Correct |
101 ms |
24268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
123 ms |
22192 KB |
Output is correct |
2 |
Correct |
118 ms |
23316 KB |
Output is correct |
3 |
Correct |
75 ms |
22216 KB |
Output is correct |
4 |
Correct |
124 ms |
25488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
707 ms |
38516 KB |
Output is correct |
2 |
Incorrect |
484 ms |
27848 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
713 ms |
37184 KB |
Output is correct |
2 |
Incorrect |
645 ms |
28740 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |