tyvj 2075差分群+二分

リンク:ここをスタンプ
P 2075[NOIP 2012 T 5]レンタル教室時間:1000 ms/空間:131072 KiB/Javaクラス名:Mainバックグラウンドnoip 2012-tg説明大学期間中、レンタル教室がしばしば必要となる.大から学部まで活動し、小から学習グループまで自習討論し、学校に教室の貸し出しを申請しなければならない.教室の大きさや機能によって、教室を借りる人の身分が異なり、教室を借りる手続きも異なります.大量のレンタル教室の情報に直面して、私たちは自然にプログラミングしてこの問題を解決することを望んでいます.次のn日間の貸し出し教室情報を処理する必要があります.そのうち、i日目には学校にri教室が貸し出しられます.m件の注文があり、各注文は3つの正の整数で記述され、それぞれdj,sj,tjであり、あるテナントがsj日目からtj日目まで教室(sj日目とtj日目を含む)を借り、毎日dj教室を借りる必要があることを示している.レンタル者は教室の大きさ、場所に要求がないと仮定します.すなわち、各注文に対して、私たちは毎日dj教室を提供するだけで、それらが具体的にどの教室なのか、毎日同じ教室なのかは考慮しないでください.教室を借りる原則は先着順、つまり注文の順番に順番に各注文に教室を割り当てることです.割り当て中に注文が完全に満たされない場合は、教室の割り当てを停止し、現在の申請者に注文の変更を通知する必要があります.ここで満足できないとは、sj日目からtj日目までの少なくとも1日の残りの教室数がdj個未満であることを意味する.注文が完全に満たされないかどうかを知る必要があります.ある場合は、どの申請者に注文を変更するかを通知する必要があります.入力フォーマット入力ファイルはclassroom.in. 最初の行には、日数と受注の数を表す2つの正の整数n,mが含まれます.2行目はn個の正の整数を含み、i番目の数はriであり、i日目に借りられる教室の数を表す.次にm行があり、各行に3つの正の整数dj,sj,tjが含まれ、レンタルの数を表し、レンタルの開始、終了はそれぞれ数日目である.各行の隣接する2つの数の間には、1つのスペースで区切られています.日数とオーダーは、1から始まる整数で指定します.出力フォーマット出力ファイルはclassroom.out. すべての注文が満たされる場合、出力は1行のみで、整数0が含まれます.それ以外の場合(受注が完全に満たされない)は2行出力され、1行目は負の整数-1を出力し、2行目は受注を変更する必要がある応募者番号を出力します.試験サンプル1入力4 3 3 2 5 4 3 3 3 3 2 4 4 4 4出力-12備考10%のデータに対して、1≦n、m≦10がある.30%のデータに対して、1≦n、m≦1000がある.70%のデータに対して、1≦n、m≦10^5がある.100%のデータに対して,1≦n,m≦10^6,0≦ri,dj≦10^9,1≦sj≦tj≦nであった.NOIP2012-TG
考え方:
最初は線分の木を書くつもりでしたが、n=1 e 6は思い切って諦めました.この問題の解説は線分の木で90点を取ることができるでしょう
毎回1区間[s,t]の日数に同数の教室を加える.num[l]+=v,num[r+1]-=vを差分数グループでm回保存した.
次にfor(1-n)は、i日目に教室の使用量を超えたか否かを処理することができ、0が出力されなければ
そうなると2点目の注文がオーバーして、毎回num差分グループで暴力的に[1,mid]の注文内の教室使用量を求めます
i日目が超えているかどうかをもう一度比較してみましょう.ここでは小さな細部を処理する必要があります.あなたの差分グループは[1,mid]しか必要ないので、[mid+1,m]はどうしますか.簡単に考えてみると、for(mid+1,m)が注文iを減算するとnum[l]-=v,num[r+1]+vになります.現在のmidを処理して加算すればいいです.
コード:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
#define INF (1ll<<60)-1
using namespace std;
int n,m;
int a[1000100],num[1000100],s[1000100],b[1000100];
struct node{
    int l,r,v;
} p[1000100];
bool solve(int x){
    for(int i=x+1;i<=m;i++){
        num[p[i].l]-=p[i].v;
        num[p[i].r+1]+=p[i].v;
    }
    int flag=0;
    for(int i=1;i<=n;i++) {
        s[i]=s[i-1]+num[i];
        if(s[i]>a[i]){
            flag=1;
        }
    }
    for(int i=x+1;i<=m;i++){
        num[p[i].l]+=p[i].v;
        num[p[i].r+1]-=p[i].v;
    }
    if(flag==0) return true;
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&p[i].v,&p[i].l,&p[i].r);
        num[p[i].l]+=p[i].v;
        num[p[i].r+1]-=p[i].v;
    }
    for(int i=1;i<=n;i++) b[i]=num[i];
    int flag=0;
    for(int i=1;i<=n;i++){
        b[i]=b[i]+b[i-1];
        if(b[i]>a[i]) {
            flag=1;
            break;
        }
    }
    if(flag==0){
        cout<<0<<endl;
        return 0;
    }
    int l=1,r=m,mid;
    while(l<r){
        int mid=(l+r)/2;
        if(solve(mid)) {
            l=mid+1;
        }
        else r=mid;
    }
    printf("-1
%d
",l);
    return 0;
}