zoj3745 Salary Increasing

OJ Problem Set - 3745

Salary Increasing

Time Limit: 2 Seconds Memory Limit: 65536 KB

Edward has established a company with n staffs. He is such a kind man that he did Q times salary increasing for his staffs. Each salary increasing was described by three integers (l, r, c). That means Edward will add c units money for the staff whose salaxy is in range [l, r] now. Edward wants to know the amount of total money he should pay to staffs after Q times salary increasing.

Input

The input file contains multiple test cases.

Each case begin with two integers : n -- which indicate the amount of staff; Q -- which indicate Q times salary increasing. The following n integers each describes the initial salary of a staff(mark as a_i). After that, there are Q triples of integers (l_i, r_i, c_i) (i=1..Q) which describe the salary increasing in chronological.

1 ≤ n ≤ 10⁵ , 1 ≤ Q ≤ 10⁵ , 1 ≤ a_i ≤ 10⁵ , 1 ≤ l_i ≤ r_i ≤ 10⁵ , 1 ≤ c_i ≤ 10⁵ , r_i < l_i+1

Process to the End Of File.

Output

Output the total salary in a line for each case.

Sample Input

4 1
1 2 3 4
2 3 4

Sample Output

Hint

{1, 2, 3, 4} → {1, 4, 6, 7}.

Author: CHEN, Weijie
Contest: ZOJ Monthly, December 2013

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=100000+10;
int num[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        int tmp;
        ll sum=0;
        memset(num,0,sizeof(num));
        for(int i=0;i<n;++i)
        {
            scanf("%d",&tmp);
            num[tmp]++;
            sum+=tmp;
        }
        int l,r,c;
        while(q--)
        {
            scanf("%d%d%d",&l,&r,&c);
            //if(l>r) swap(l,r);
            for(int i=r;i>=l;--i)
            {
                sum+=(ll)c*num[i];
                if(i+c<maxn) num[i+c]+=num[i];
                num[i]=0;
            }
        }
        printf("%lld
",sum);
    }
    return 0;
}