#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
struct node {
int s, e;
ll mn, mx, sum;
bool lset;
ll add_val, set_val;
node *l, *r;
node (int _s, int _e, int A[] = NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL) {
if (A == NULL) return;
if (s == e) mn = mx = sum = A[s];
else {
l = new node(s, (s+e)>>1, A), r = new node((s+e+2)>>1, e, A);
combine();
}
}
void create_children() {
if (s == e) return;
if (l != NULL) return;
int m = (s+e)>>1;
l = new node(s, m);
r = new node(m+1, e);
}
void self_set(ll v) {
lset = 1;
mn = mx = set_val = v;
sum = v * (e-s+1);
add_val = 0;
}
void self_add(ll v) {
if (lset) { self_set(v + set_val); return; }
mn += v, mx += v, add_val += v;
sum += v*(e-s+1);
}
void lazy_propagate() {
if (s == e) return;
if (lset) {
l->self_set(set_val), r->self_set(set_val);
lset = 0;
set_val = 0;
}
if (add_val != 0) {
l->self_add(add_val), r->self_add(add_val);
add_val = 0;
}
}
void combine() {
if (l == NULL) return;
sum = l->sum + r->sum;
mn = min(l->mn, r->mn);
mx = max(l->mx, r->mx);
}
void add(int x, int y, ll v) {
if (s == x && e == y) { self_add(v); return; }
int m = (s+e)>>1;
create_children(); lazy_propagate();
if (x <= m) l->add(x, min(y, m), v);
if (y > m) r->add(max(x, m+1), y, v);
combine();
}
void set(int x, int y, ll v) {
if (s == x && e == y) { self_set(v); return; }
int m = (s+e)>>1;
create_children(); lazy_propagate();
if (x <= m) l->set(x, min(y, m), v);
if (y > m) r->set(max(x, m+1), y, v);
combine();
}
ll range_sum(int x, int y) {
if (s == x && e == y) return sum;
if (l == NULL || lset) return (sum / (e-s+1)) * (y-x+1);
int m = (s+e)>>1;
lazy_propagate();
if (y <= m) return l->range_sum(x, y);
if (x > m) return r->range_sum(x, y);
return l->range_sum(x, m) + r->range_sum(m+1, y);
}
ll range_min(int x, int y) {
if (s == x && e == y) return mn;
if (l == NULL || lset) return mn;
int m = (s+e)>>1;
lazy_propagate();
if (y <= m) return l->range_min(x, y);
if (x > m) return r->range_min(x, y);
return min(l->range_min(x, m), r->range_min(m+1, y));
}
ll range_max(int x, int y) {
if (s == x && e == y) return mx;
if (l == NULL || lset) return mx;
int m = (s+e)>>1;
lazy_propagate();
if (y <= m) return l->range_max(x, y);
if (x > m) return r->range_max(x, y);
return max(l->range_max(x, m), r->range_max(m+1, y));
}
~node() {
if (l != NULL) delete l;
if (r != NULL) delete r;
}
void scrap(){
mn= mx=sum=lset=0;
add_val=0;
set_val=0;
if(l!=NULL){
l->scrap();
r->scrap();
}
}
} *root;
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
vector<int> arr[n+1];
for(int i=1; i<=m; i++){
int x;
cin >> x;
arr[x].push_back(i);
}
ll need[n+1];
for(int i=1; i<=n; i++) cin >> need[i];
int q;
cin >> q;
pair<pair<int,int>,ll> qu[q+1];
for(int i=1; i<=q; i++){
int a,b;
ll c;
cin >> a >> b >> c;
qu[i]={{a,b},c};
}
root=new node(1,m);
int lo[n+1],hi[n+1];
for(int i=1; i<=n; i++) lo[i]=1,hi[i]=q+1;
for(int k=0; k<20; k++){
pair<int,int> whr[n+1];
for(int i=1; i<=n; i++){
whr[i]={(lo[i]+hi[i])/2,i};
}
sort(whr+1,whr+n+1);
int c=1;
root->scrap();
for(int i=1; i<=n; i++){
if(lo[whr[i].second]==hi[whr[i].second]) continue;
while(c<=min(q,whr[i].first)){
if(qu[c].first.first<=qu[c].first.second) root->add(qu[c].first.first,qu[c].first.second,qu[c].second);
else{
root->add(1,qu[c].first.second,qu[c].second);
root->add(qu[c].first.first,m,qu[c].second);
}
c++;
}
ll heh=0;
for(int j:arr[whr[i].second]) heh+=root->range_sum(j,j);
if(heh>=need[whr[i].second]) hi[whr[i].second]=whr[i].first;
else lo[whr[i].second]=whr[i].first+1;
}
}
for(int i=1; i<=n; i++){
if(lo[i]==q+1) cout << "NIE\n";
else cout << lo[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Output is correct |
| 2 |
Correct |
5 ms |
468 KB |
Output is correct |
| 3 |
Correct |
5 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Output is correct |
| 2 |
Correct |
5 ms |
468 KB |
Output is correct |
| 3 |
Correct |
5 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
582 ms |
9476 KB |
Output is correct |
| 2 |
Correct |
828 ms |
11596 KB |
Output is correct |
| 3 |
Correct |
832 ms |
10256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
704 ms |
10048 KB |
Output is correct |
| 2 |
Correct |
725 ms |
9884 KB |
Output is correct |
| 3 |
Correct |
903 ms |
11616 KB |
Output is correct |
| 4 |
Correct |
108 ms |
5540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
10244 KB |
Output is correct |
| 2 |
Correct |
458 ms |
12100 KB |
Output is correct |
| 3 |
Correct |
102 ms |
1748 KB |
Output is correct |
| 4 |
Correct |
732 ms |
10500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
8820 KB |
Output is correct |
| 2 |
Correct |
646 ms |
11016 KB |
Output is correct |
| 3 |
Correct |
684 ms |
9368 KB |
Output is correct |
| 4 |
Correct |
806 ms |
11904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6042 ms |
65332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6005 ms |
64348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
