「NOIP2012」「LuoguP1083」 借教室

Description

在大學期間，經常需要租借教室。大到院系舉辦活動，小到學習小組自習讨論，都需要向學校申請借教室。教室的大小功能不同，借教室人的身份不同，借教室的手續也不一樣。

面對海量租借教室的資訊，我們自然希望程式設計解決這個問題。

我們需要處理接下來 nnn 天的借教室資訊，其中第 iii 天學校有 rir_iri​ 個教室可供租借。共有 mmm 份訂單，每份訂單用三個正整數描述，分别為 dj,sj,tjd_j,s_j,t_jdj​,sj​,tj​ ，表示某租借者需要從第 sjs_jsj​ 天到第 tjt_jtj​ 天租借教室（包括第 sjs_jsj​ 天和第 tjt_jtj​ 天），每天需要租借 djd_jdj​ 個教室。

我們假定，租借者對教室的大小、地點沒有要求。即對于每份訂單，我們隻需要每天提供 djd_jdj​ 個教室，而它們具體是哪些教室，每天是否是相同的教室則不用考慮。

借教室的原則是先到先得，也就是說我們要按照訂單的先後順序依次為每份訂單配置設定教室。如果在配置設定的過程中遇到一份訂單無法完全滿足，則需要停止教室的配置設定，通知目前申請人修改訂單。這裡的無法滿足指從第 sjs_jsj​ 天到第 tjt_jtj​ 天中有至少一天剩餘的教室數量不足 djd_jdj​ 個。

現在我們需要知道，是否會有訂單無法完全滿足。如果有，需要通知哪一個申請人修改訂單。

Input

第一行包含兩個正整數 n,mn,mn,m ，表示天數和訂單的數量。

第二行包含 nnn 個正整數，其中第 iii 個數為 rir_iri​ ，表示第 iii 天可用于租借的教室數量。

接下來有 mmm 行，每行包含三個正整數 dj,sj,tjd_j,s_j,t_jdj​,sj​,tj​ ，表示租借的數量，租借開始、結束分别在第幾天。

每行相鄰的兩個數之間均用一個空格隔開。天數與訂單均用從 111 開始的整數編号。

Output

如果所有訂單均可滿足，則輸出隻有一行，包含一個整數 0 00 。否則（訂單無法完全滿足）

輸出兩行，第一行輸出一個負整數 −1-1−1 ，第二行輸出需要修改訂單的申請人編号。

Sample Input

4 3

2 5 4 3

2 1 3

3 2 4

4 2 4

Sample Output

-1

2

Hint

【輸入輸出樣例說明】

第 1 份訂單滿足後， 4 天剩餘的教室數分别為 0,3,2,3。第 2 份訂單要求第 2 天到第 4 天每天提供 3 個教室，而第 3 天剩餘的教室數為 2 ，是以無法滿足。配置設定停止，通知第 2 個申請人修改訂單。

【資料範圍】

對于10%的資料，有 1≤n,m≤10；

對于30%的資料，有 1≤n,m≤1000；

對于 70%的資料，有 1≤n,m≤1e5；

對于 100%的資料，有 1≤n,m≤1e6,0≤ri,dj≤1e9,1≤sj≤tj≤n。

NOIP 2012 提高組 第二天 第二題

題解

題意：

給定序列 和m個操作 每個操作将序列中從s~t的值-d，要求按順序操作。
求最早在何時序列中有負數。
           

考慮使用差分實作O(1)修改，則目前值為字首和。

首先在讀入序列時，我們對于每個讀入的x，a[ i ]+=x,a[ i + 1 ] -=x ;

對于每個操作，我們在讀入時就做一遍( a [ s [ i ] ] - = d [ i ] ; a [ t [ i ] + 1 ] + = d [ i ] )，壓棧。

最後為了迎合字首和，我們從1到n周遊坐标，若目前坐标時的字首和為負，則一直彈棧并做原操作的逆操作，直到目前字首和為正為止。

注意如果彈到的目前操作的s或t小于目前坐标的話，修改a[s]或a[t]沒有用，直接修改sum。

複雜度O(n+m)。

#include<cstdio>
#include<iostream>
using namespace std;
#define R register
const int MAXN=;
int a[MAXN];
int d[MAXN],s[MAXN],t[MAXN];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int x;
    for(R int i=;i<=n;++i)
    {
        scanf("%d",&x);
        a[i]+=x;
        a[i+]-=x;
    }
    for(R int i=;i<=m;++i)
    {
        scanf("%d%d%d",&d[i],&s[i],&t[i]);
        a[s[i]]-=d[i];
        a[t[i]+]+=d[i];
    }
    int j=m;
    int sum=;
    for(R int i=;i<=n;++i)
    {
        while(sum+a[i]<&&j)
        {
            a[s[j]]+=d[j];
            a[t[j]+]-=d[j];
            if(s[j]<i)a[i]+=d[j];
            if(t[j]+<i)a[i]-=d[j];
            j--;
        }
        sum+=a[i];
    }
    if(j==m){cout<<;return ;}
    cout<<-<<endl<<j+;return ;
}