!Parallel Binary Search

#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <string>
#include <cstring>
#include <set>

using namespace std;

typedef long long ll;
typedef double ld;

const ll INF = 1e9 + 9;
const int N = 300001;

vector<int> g[N], need[N];
int l[N],r[N], L[N], R[N], m;
ll cnt[N], a[N], tree[N];

void upd(int x, ll val)
{
    while (x <= m)
    {
        tree[x] += val;
        x += (x & -x);

    }
}
ll get(int x)
{
    ll s = 0;
    while (x)
    {
        s+=tree[x];
        x-=(x & -x);
    }
    return s;
}

int main()
{
  //  freopen("in.txt", "r", stdin);
    int n;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        g[x].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        cin >> cnt[i];
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> l[i] >> r[i] >> a[i];
    for (int i = 0; i <= n; i++)
        L[i] = 1, R[i] = k + 1;
    bool ok = 1;
    while (ok)
    {
        ok = 0;
        for(int i = 0; i < N; i++)
            tree[i] = 0;
        for(int i = 1; i <= n; i++)
            if(L[i] != R[i])
                need[(L[i] + R[i]) / 2].push_back(i);
        for (int i = 1; i <= k; i++)
        {
            if (l[i] <= r[i])
            {
                upd(l[i], a[i]);
                upd(r[i] + 1, -a[i]);
            }
            else
            {
                upd(1, a[i]);
                upd(r[i] + 1, -a[i]);
                upd(l[i], a[i]);
            }
            while (need[i].size())
            {
                int cur = need[i].back();
                need[i].pop_back();
                ll sum = 0;
                ok = 1;
                for (auto sectors: g[cur])
                {
                    sum += get(sectors);
                    if(sum >= cnt[cur])
                        break;
                }
                if (sum >= cnt[cur])
                    R[cur] = i;
                else
                    L[cur] = i + 1;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(L[i] <= k)
            cout << L[i] << "\n";
        else
            cout << "NIE\n";
    }
    return 0;