Imperishable Night

第一行包含两个正整数n和q，之间使用一个空格符分隔，分别为盒子的数目以及操作的次数。
第二行开始连续q行，每行包含三个整数，相邻整数之间使用一个空格符分隔，这样输入的第i行的三个整数按照输入顺序记作 $l_i,\ r_i,\ k_i$ 。

数据规范：
* $1 \le n \le 10^6$ .
* $1 \le q \le 10^6$ .
* $l_i \le r_i$ .
* $0 \le k_i \le 10^6$ .
* $1 \le l_i,\ r_i \le n$ .
* 保证完成所有操作后全部盒子中的钻石数目之和不超过 $10^9$ .

C++14(g++5.4) 解法, 执行用时: 569ms, 内存消耗: 9240K, 提交时间: 2019-12-08 09:59:40

#include <stdio.h>
int a[1000000];
int main(){
	int n,q,k,l,r;
	scanf("%d%d", &n, &q);
	while(q--){
		scanf("%d%d%d", &l,&r,&k);
		a[l]+=k;
		a[r+1]-=k;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=a[i];
		if(i==1)
			printf("%d", sum);
		else
			printf(" %d", sum);
	}
	return 0;
}

C(clang 3.9) 解法, 执行用时: 564ms, 内存消耗: 10264K, 提交时间: 2019-12-12 21:07:03

#include<stdio.h>
int s[1000010];
int main()
{
	int m,n,k,a,b,c,i;
	scanf("%d%d",&m,&n);
	while(n--)
	{
		scanf("%d%d%d",&a,&b,&c);
		s[a]+=c;
		s[b+1]-=c;
	}
	printf("%d",s[1]);
	for(i=2;i<=m;i++)
	{
		s[i]+=s[i-1];
		printf(" %d",s[i]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 388ms, 内存消耗: 9196K, 提交时间: 2019-12-07 12:46:10

#include<stdio.h>
int a[1000050];
int main(){
	int n,k,l,r,q;
	int sum=0;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&l,&r,&k);
		a[l]+=k;
		a[r+1]-=k;
	}
	for(int i=1;i<=n;i++){
		sum+=a[i];
		printf("%d ",sum);
	}
	return 0;
}

详情