89. D.小雞的潛力

0 Judge

Code: 0

本題狀態

統計

D.小雞的潛力

本題需要重新測定時限!

sprout

題目敘述

咖波覺得計算小雞的飽足感有點累。好險聰明的咖波很快就發現更好的方法。

咖波發現，小雞是可以合成和分割的。於是他這麼做：

咖波先把N隻大小不同的小雞排成一直線，飽足感由左至右為$H_1,H_2,\cdots H_n$，咖波可以任選連續的小雞$H_l,H_{l+1},H_{l+2}.....H_r$，把這些小雞的大小同時增加或減少一個數值$V$。要是小雞變得太小，飽足感也可能會小於零(消化的耗能還比不上得到的能量)。

最後咖波想知道最大的小雞和最小的小雞，相差多少飽足感。但是咖波只想快點繼續進食。你能幫咖波解決這個問題嗎？

實作說明

你必須上傳一個指定函數，其函數原型如下：

int Answer(int N,int P,int *H,int *L,int *R,int *V);

參數意義代表如下：

  • N：小雞的數量
  • P：修改的次數
  • H[0],H[1]...H[N−1]：小雞一開始的大小
  • L[0],L[1]...L[P−1]：每次修改的左界
  • R[0],R[1]...R[P−1]：每次修改的右界
  • V[0],V[1]...V[P−1]：每次修改增加的大小

回傳值意義代表如下：

一個整數，為完成操作後，最大和最小的小雞大小差多少。

我們可以參考這一個範例：

N=5
P=3
H[]={0,0,1,0,1}
L[]={1,2,1}
R[]={3,5,1}
V[]={1,−1,2}

代表有5隻小雞，大小分別為{0,0,1,0,1}，接下來有3次修改。

第一次修改的區間為$H_1∼H_3$，增加大小$1$，修改完後小雞大小為{1,1,2,0,1}

第二次修改的區間為$H_2∼H_5$，增加大小$-1$，修改完後小雞大小為{1,0,1,−1,0}

第三次修改的區間為$H_1∼H_1$，增加大小$2$，修改完後小雞大小為{3,0,1,−1,0}

於是答案為最大減最小，即$3−(−1)=4$。

限制

函式被使用的次數不超過一次

  • $1\leq N\leq 10^6$
  • $0\leq P\leq 10^6$
  • $−100\leq H[i]\leq 100$
  • $1\leq L[i]\leq R[i]\leq N$
  • $−100\leq V[i]\leq 100$

範例程式

為方便您撰寫此題，下提供範例程式，在指定位置撰寫您的程式碼即可。下提供測試資料的輸入方法。

範例程式輸入

第一行有兩個數字：$N,P$，接下來下一行有$N$個數字，分別代表$H[i]$的數值，在接下來有$P$行，每行有三個數字，分別為$L[i],R[i],V[i]$

範例程式輸出

直接輸出Answer的回傳值。

範例輸入

5 3
0 0 1 0 1
1 3 1
2 5 -1
1 1 2

範例輸出

4

配分:

配分 限制
9% $N \leq 5, P = 1$
11% $N \leq 5$
15% $P=0$
15% $P \leq 10^4$
20% 修改的區間全部不相交
30% 沒有限制

參考程式碼

#ifndef EVAL
#include<iostream>
using std::cin;
using std::cout;
using std::endl;
int Answer(int N,int P,int *H,int *L,int *R,int *V);

int main()
{
    const int maxN = 1000000;
    const int maxP = 1000000;
    int *H = new int[maxN];
    int *L = new int[maxP];
    int *R = new int[maxP];
    int *V = new int[maxP];
    int N,P;
    while( cin>>N>>P )
    {
        for(int i=0;i<N;++i)
            cin>>H[i];
        for(int i=0;i<P;++i)
            cin>>L[i]>>R[i]>>V[i];
        cout<<Answer(N,P,H,L,R,V)<<endl;
    }
}
#endif
/*================================================================*/
/*================================================================*/
/*================================================================*/
/*================================================================*/
/*Write Your Program Here*/
/*Notice: You should include header for yourself*/

int Answer(int N,int P,int *H,int *L,int *R,int *V)
{
}

Source


Judge Setting

run-time limit: 300 ms
memory limit: 51200000 byte
測資數量: 0