Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 300005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, m;
- int bl[N], gr[N], wh[N];
- int h[3000005];
- int b[3000005];
- int c[3000005];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n;
- for(int i=1; i<=n; i++) cin >> bl[i];
- for(int i=1; i<=n; i++) cin >> gr[i];
- for(int i=1; i<=n; i++) cin >> wh[i];
- for(int i=1; i<=n; i++){
- h[bl[i]]++;
- h[bl[i]+gr[i]]+=2;
- h[bl[i]]-=2;
- h[bl[i]+gr[i]+wh[i]]+=5;
- h[bl[i]+gr[i]]-=5;
- }
- for(int i=3000000; i>=1; i--) h[i] += h[i+1];
- }
- int tr[3000005*4];
- void build(int id, int l, int r){
- if (r==l){
- tr[id] = 1;
- return;
- }
- int mid = (l+r)/2;
- build(id*2,l,mid);
- build(id*2+1,mid+1,r);
- tr[id] = tr[id*2] + tr[id*2+1];
- }
- void up(int id, int l, int r, int u){
- if (r < u || u < l) return;
- if (r==l && l==u){
- tr[id] = 0;
- return;
- }
- int mid = (l+r)/2;
- up(id*2,l,mid,u);
- up(id*2+1,mid+1,r,u);
- tr[id] = tr[id*2] + tr[id*2+1];
- }
- int get(int id, int l, int r, int val){
- if (l > r) return -1;
- if (tr[id] < val) return -1;
- if (l==r) return l;
- int mid = (l+r)/2;
- if (tr[id*2] < val){
- val -= tr[id*2];
- return get(id*2+1,mid+1,r,val);
- }
- return get(id*2,l,mid,val);
- }
- void proc()
- {
- int q; cin >> q;
- int ans = 0;
- int Pmax = 3000000;
- build(1,1,Pmax);
- while (q--){
- int hi; cin >> hi;
- int p = get(1,1,Pmax,hi);
- if (p==-1){
- cout << 0 << '\n';
- }
- else{
- cout << h[p] << '\n';
- up(1,1,Pmax,p);
- }
- }
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement