(POI) XVIII OI Meteors [整體二分]

https://szkopul.edu.pl/problemset/problem/7JrCYZ7LhEK4nBR5zbAXpcmM/site/?key=statement

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PiL(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)
#define REP(L,R,k) for (int i = (L); (R) >= i; i+= (k) )

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

const int N = 3e5 + 6;

struct BIT {
    int n;
    LL a[N];
    void init(int n) {
        this->n = n;
        MEM0(a);
    }
    void add(int pos,int val) {
        for (int i=pos;n>=i;i+=i&(-i)) {
            a[i] += val;
        }
    }
    LL qry(int pos) {
        LL ret=0;
        for (int i=pos;i>=1;i-=i&(-i)) {
            ret += a[i];
        }
        return ret;
    }
    LL query(int L,int R) {
        return qry(R) - qry(L-1);
    }
} bit;

int owner[N];
int goal[N];
int n,m;
int qL[N],qR[N],qX[N];
vint has_land[N];

void do_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        //cout<<"i = "<<i<<endl;
        int nl=qL[i],nr = qR[i];
        int nx=qX[i];
        //cout<<"nl = "<<nl<<" , nr = "<<nr<<" , nx = "<<nx<<endl;
        if (nr >= nl) {
            bit.add(nl,nx);
            bit.add(nr+1,-nx);
        }
        else if (nl > nr) {
            bit.add(1,nx);
            bit.add(nr+1,-nx);
            bit.add(nl,nx);
            bit.add(m+1,-nx);
        }

    }
}

void undo_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        int nl=qL[i],nr = qR[i];
        int nx=qX[i];
        bit.add(nl,-nx);
        bit.add(nr+1,nx);
        if (nl > nr) {
            bit.add(1,-nx);
            //bit.add(m+1,-nx);
        }
    }
}

LL tmp[N];
int ans[N];

void split(int mid,vint& persons,vint &ok,vint &notok) {
    //cout<<"mid = "<<mid<<endl;
    for (int p:persons) {
        tmp[p] = 0;
        for (int it:has_land[p]) {
            tmp[p] += bit.qry(it);
            //cout<<"it = "<<it<< " , query = "<<bit.qry(it)<<endl;
            if (tmp[p] >= goal[p]) break;
        }
        if (tmp[p] >= goal[p]) {
            ok.PB(p);
            if (ans[p] > 0) {
                ans[p] = min(ans[p],mid);
            }
            else {
                ans[p] = mid;
            }
        }
        else {
            goal[p] -= tmp[p];
            notok.PB(p);
        }
    }
    //cout<<"after mid , ok : ";for(int i:ok) cout<<i<<' ';cout<<" , notok : ";for (int i:notok)cout<<i<<' ';
    //cout<<endl;
    vector<int> ().swap(persons);  //release memory
}

void totBS(int L,int R,vint persons) {
    //cout<<"L = "<<L<<" , R =  "<<R<<endl;
    if (L > R || SZ(persons) == 0) return;
    int mid =(L+R) >> 1;
    //cout<<"mid = "<<mid<<endl;
    do_things(L,mid);
    vint ok,notok;
    split(mid,persons,ok,notok);
    undo_things(L,mid);
    totBS(L,mid-1,ok);
    totBS(mid+1,R,notok);
}

int main () {
    //srand(time(NULL));
    Sii(n,m);
    bit.init(m+1);
    REP1(i,m) {
        Si(owner[i]);
        has_land[ owner[i] ].PB(i);
    }
    REP1(i,n) {
        Si(goal[i]);
    }
    int k;
    Si(k);
    REP1(i,k) {
        Siii(qL[i],qR[i],qX[i]);
    }
    vint persons;
    REP1(i,n) persons.PB(i);
    totBS(1,k,persons);
    REP1(i,n) {
        //cout<<"I = "<<i<<" , goal = "<<goal[i]<<endl;
        if (ans[i] == 0) puts("NIE");
        else Pi(ans[i]);
    }
}