Meteors

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define pb push_back
#define SZ(x) ((int)x.size())

// ----------------------------------------------------------------------------------------------------------

const int MAX = 300005;
int M, N, Q;
ll Add[MAX], Done[MAX], Goal[MAX], L[MAX], R[MAX], V[MAX];
vector<ll> A(MAX,0), B(MAX,0), Meteors[MAX];

int main()
{
    scanf("%d%d", &N, &M);

    f(i,1,M)
    {
        int own;
        scanf("%d", &own);
        Meteors[own].pb(i);
    }

    f(i,1,N) scanf("%d", &Goal[i]);

    scanf("%d", &Q);
    f(q,1,Q) scanf("%d%d%d",&L[q],&R[q],&V[q]);

    int block = sqrt(Q);

    for(int from = 1; from <= Q; from += block)
    {
        int to = min(Q, from+block-1);

        f(i,0,M) Add[i] = 0;
        B = A;

        f(i,from,to)
        {
            if(L[i] <= R[i]) Add[L[i]] += V[i], Add[R[i]+1] -= V[i];
            else
            {
                Add[1] += V[i], Add[R[i]+1] -= V[i];
                Add[L[i]] += V[i], Add[M+1] -= V[i];
            }
        }

        f(i,1,M)
        {
            Add[i] += Add[i-1];
            B[i] += Add[i];
        }

        f(c,1,N) if(!Done[c])
        {
            ll tot = 0;

            f(i,0,SZ(Meteors[c])-1)
            {
                int m = Meteors[c][i];
                tot += B[m];
            }

            if(tot >= Goal[c])
            {
                ll am = 0;

                f(i,0,SZ(Meteors[c])-1)
                {
                    int m = Meteors[c][i];
                    am += A[m];
                }

                f(r,from,to)
                {
                    f(i,0,SZ(Meteors[c])-1)
                    {
                        int m = Meteors[c][i];
                        if(R[r] >= L[r] && m >= L[r] && m <= R[r]) am += V[r];
                        else if(R[r] < L[r] && (m >= L[r] || m <= R[r])) am += V[r];
                    }
                    if(am >= Goal[c])
                    {
                        Done[c] = r;
                        break;
                    }
                }
            }
        }

        A = B;
    }

    f(i,1,N)
        if(Done[i]) printf("%d\n", Done[i]);
        else printf("NIE\n");
}