codeforces 589 G(birnary serach+bit+オフライン)

タイトル:
n,m(n,m<=2 e 5)が与えられていることは明らかである.
長さmの配列を指定し、m日一人がどのくらい働けるかを表します.
以下にn対の二元グループがあり、(d,t)はi番目の人を代表して仕事量tの任務を完成する必要があるが、毎日やらないか、dの時間を出して準備し、残りの実行可能な時間は仕事をして、一人一人に少なくとも数日目に任務を完成する必要があると聞いた.
分析:このようなテーマは、明らかな考え方で、オフラインソートによって順序化され、一方から考えて、はいの前に後の条件を兼ねて、点データ構造を加えればACになります.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define rep1(i,x,y) for(int i=x;i<=y;i++)
#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long ll;
using namespace std;
#define lowbit(x) (x&(-x))
const int N = 2e5 + 1000;
#define int long long
typedef pair<int,int> pii;
#define val first
#define id second
pii a[N];
pair<pii,int> b[N];
int n,ans[N],m;
struct bit_
{
    int C[N];
    void init()
    {
        memset(C,0,sizeof(C));
    }
    int sum(int x)
    {
        int ret = 0;
        while(x >0)
        {
            ret += C[x];
            x-=lowbit(x);
        }
        return ret;
    }
    void add(int x,int d)
    {
        while(x <= m)
        {
            C[x] +=d;
            x+=lowbit(x);
        }
    }
} c , cnt;
main()
{
   cin>>n>>m;
    rep1(i,1,m)
    {
        int d;
       cin>>d;
        a[i]=pii(d,i);
    }
    rep1(i,1,n)
    {
        int x, y;
       cin>>x>>y;
        b[i] = make_pair(pii(x,y),i);
    }
    sort(a+1,a+1+m);
    sort(b+1,b+1+n);
    c.init(); cnt.init();
    int posi = m;
    for(int i=n; i>=1; i--)
    {
        pii te = b[i].first;
        int lim = te.first;
        while(posi && a[posi].val>lim)
        {
            c.add(a[posi].id,a[posi].val);
            cnt.add(a[posi].id,1);
            posi--;
        }
        if(c.sum(m) - (m-posi)*lim < te.second)
        {
            ans[b[i].second ] = 0;
            continue;
        }
        else
        {
            int x = 0, y=m;
            while(x < y)
            {
                int mid = (x+y)>>1;
                if(c.sum(mid) - (cnt.sum(mid)*lim)<te.second ) x = mid+1;
                else y=mid;
            }
           ans[b[i].second ] = x;
        }
    }
    rep1(i,1,n) {
        if(i>1) printf(" ");
        printf("%d",(int)ans[i]);
    }
}