#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define SZ(v) (int)v.size()
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
const int MX = 200005;
int n,q,a[MX];
int seg[100*MX],lft[100*MX],rgt[100*MX],lazy[100*MX];
int SZ = 1;
void propagate(int ind,int l,int r){
if(l != r){
if(!lft[ind]) lft[ind] = ++SZ;
if(!rgt[ind]) rgt[ind] = ++SZ;
}
if(lazy[ind] == -1) return;
if(lazy[ind] == 1) seg[ind] = (r-l+1);
else seg[ind] = 0;
if(l != r){
lazy[lft[ind]] = lazy[ind];
lazy[rgt[ind]] = lazy[ind];
}
lazy[ind] = -1;
}
int update0(int ind,int l,int r,int val){
propagate(ind,l,r);
int ret = seg[ind];
if(seg[ind] <= val){
// cout << ind << " " << l << " " << r << " " << val << " -0\n";
lazy[ind] = 0;
propagate(ind,l,r);
return ret;
}
if(l == r) return ret;
int mid = (l+r)/2;
int sml = update0(lft[ind],l,mid,val);
if(sml < val){
val -= sml;
update0(rgt[ind],mid+1,r,val);
}
else{
propagate(rgt[ind],mid+1,r);
}
seg[ind] = seg[lft[ind]]+seg[rgt[ind]];
// cout << "update0:: " << ind << " " << l << " " << r << " " << seg[ind] << "\n";
return ret;
}
int update1(int ind,int l,int r,int val){
propagate(ind,l,r);
int ret = seg[ind];
if(seg[ind] >= r-val){
// cout << ind << " " << l << " " << r << " " << val << " -1\n";
lazy[ind] = 1;
propagate(ind,l,r);
return ret;
}
if(l == r) return ret;
int mid = (l+r)/2;
int sml = update1(lft[ind],l,mid,val);
if(sml > mid-val){
val += sml;
update1(rgt[ind],mid+1,r,val);
}
else{
propagate(rgt[ind],mid+1,r);
}
seg[ind] = seg[lft[ind]]+seg[rgt[ind]];
// cout << "update1:: " << ind << " " << l << " " << r << " " << seg[ind] << "\n";
return ret;
}
int query(int ind,int l,int r,int pos){
propagate(ind,l,r);
if(l > pos) return 0;
// cout << ind << " " << l << " " << r << " " << pos << " " << seg[ind] << "\n";
if(r <= pos) return seg[ind];
int mid = (l+r)/2;
return query(lft[ind],l,mid,pos)+query(rgt[ind],mid+1,r,pos);
}
vector<signed> distribute_candies(vector<signed> c,vector<signed> l,vector<signed> r,vector<signed> v){
n = c.size();
q = l.size();
REP(j,q){
if(v[j] < 0) update0(1,1,1e9,-v[j]);
else update1(1,1,1e9,v[j]);
}
vector<signed> ans;
REP(i,n){
ans.pb(query(1,1,1e9,c[i]));
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
417 ms |
138452 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
386 ms |
46948 KB |
Output is correct |
4 |
Correct |
311 ms |
104268 KB |
Output is correct |
5 |
Correct |
365 ms |
48480 KB |
Output is correct |
6 |
Correct |
677 ms |
133292 KB |
Output is correct |
7 |
Correct |
978 ms |
312020 KB |
Output is correct |
8 |
Correct |
362 ms |
48424 KB |
Output is correct |
9 |
Correct |
582 ms |
300748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |