#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 300030;
long long loga[maxn];
void update(int x, int val){
for (; x < 2 * maxn; x += (x & (-x))){
loga[x] += val;
}
}
long long query(int x){
long long ret = 0;
for (; x > 0; x -= (x & (-x))){
ret += loga[x];
}
return ret;
}
vector<int> d[maxn];
long long p[maxn];
int l[maxn];
int r[maxn];
int a[maxn];
int lo[maxn];
int hi[maxn];
int mid[maxn];
vector<int> mn[maxn];
vector<pair<int, int > > nmn;
int sol[maxn];
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
int x;
cin >> x;
d[x].push_back(i);
}
for (int i = 1; i <= n; i++){
cin >> p[i];
}
int k;
cin >> k;
for (int i = 1; i <= k; i++){
cin >> l[i] >> r[i] >> a[i];
}
for (int i = 1; i <= n; i++){
lo[i] = 0;
hi[i] = k + 1;
mid[i] = (lo[i] + hi[i]) / 2;
mn[mid[i]].push_back(i);
}
//cout << 77 << endl;
int lg = (int)log2((double)k) + 3;
//cout << " " << lg << endl;
for (int j = 0; j < lg; j++){
//cerr << "j " << j << "\n";
//cout << mn[k].size() << endl;
for (int i = 1; i <= k; i++){
//cerr << i << "\n";
if (l[i] <= r[i]){
update(l[i], a[i]);
update(r[i] + 1, -a[i]);
}
else {
update(l[i], a[i]);
update(m + 1, -a[i]);
update(1, a[i]);
update(r[i] + 1, -a[i]);
}
/*if (i == 3){
for (int e = 1; e <= 3; e++){
long long z = 0;
for (int f = 0; f < d[e].size(); f++){
z += query(d[e][f]);
}
cout << "Z " << e << " " << z << endl;
}
}*/
//cerr << "555" << endl;
//cerr << "Mn " << mn[i].size() << endl;
for (int t = 0; t < mn[i].size(); t++){
//cerr << "T " << t << endl;
int e = mn[i][t];
long long z = 0;
for (int f = 0; f < d[e].size(); f++){
z += query(d[e][f]);
}
/*if (e == 1 && i == 3){
cout << "da" << endl;
}*/
if (z >= p[e]){
sol[e] = i;
hi[e] = i;
nmn.push_back(make_pair((lo[i] + hi[i]) / 2, i));
}
else {
lo[e] = i + 1;
//cout << "mid " << (lo[i] + hi[i] / 2) << endl;
nmn.push_back(make_pair((lo[i] + hi[i]) / 2, i));
}
}
//cerr << "666" << endl;
mn[i].clear();
//cerr << "777" << endl;
}
for (int t = 0; t < nmn.size(); t++){
mn[nmn[t].first].push_back(nmn[t].second);
}
nmn.clear();
memset(loga, 0, sizeof(loga));
}
for (int i = 1; i <= n; i++){
if (sol[i] > 0){
cout << sol[i] << "\n";
}
else {
cout << "NIE\n";
}
}
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:98:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int t = 0; t < mn[i].size(); t++){
| ~~^~~~~~~~~~~~~~
met.cpp:103:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int f = 0; f < d[e].size(); f++){
| ~~^~~~~~~~~~~~~
met.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int t = 0; t < nmn.size(); t++){
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
29 ms |
29292 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
32 ms |
29316 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
54 ms |
31300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
50 ms |
31852 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
51 ms |
31588 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
55 ms |
31084 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1124 ms |
54720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1057 ms |
53556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
