# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1128535 | rasbery303 | 새로운 문제 (POI11_met) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long int;
const int maxn = 3e5+1;
int n, m, k;
ll tree[maxn], p[maxn];
vector<int> own[maxn], check[maxn];
int ql[maxn], qr[maxn], l[maxn], r[maxn];
ll qval[maxn];
void update(int x, long long val){
while(x<=m){
tree[x]+=val;
x+=(x&-x);
}
}
long long read(int x){
long long s=0;
while(x>0){
s+=tree[x];
x-=(x&-x);
}
return s;
}
void apply(int x){
if(ql[x]<=qr[x])
update(ql[x],qval[x]),update(qr[x]+1,-qval[x]);
else{
update(1,qval[x]);
update(qr[x]+1,-qval[x]);
update(ql[x],qval[x]);
}
}
int main(){
cin >> n >> m;
a.resize(m+1), p.resize(n+1);
for (int i = 1; i <= m; ++i){
int x;
cin >> x;
own[x].push_back(i);
}
for (int i = 1; i <= n; ++i)
cin >> p[i];
cin >> k;
for (int i = 1; i <= k; ++i)
cin >> ql[i] >> qr[i] >> qval[i];
for (int i = 1; i <= n; ++i){
l[i] = 1;
r[i] = k+1;
}
bool ok = true;
while (ok){
ok = false;
for (int i = 0; i <= m; ++i)
tree[i] = 0;
for (int i = 1; i <= n; ++i){
if (l[i]!=r[i]){
int mid = (l[i]+r[i])>>1;
check[mid].push_back(i);
}
}
for (int q = 1; q <= k; ++q){
apply(q);
while(!check[q].empty()){
ok = true;
int id = check[q].back();
check[q].pop_back();
ll sum = 0;
for (auto sec: own[id]){
sum += read(sec);
if (sum >= p[id]) break;
}
if (sum >= p[id])
r[id] = q;
else
l[id] = q+1;
}
}
}
for (int i = 1; i <= n; ++i){
if (l[i] <= k){
cout << l[i] << '\n';
} else {
cout << "NIE\n";
}
}
}