Submission #1170607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170607		zrzzrz	Lasers (NOI19_lasers)	C++20	100 / 100	900 ms	19932 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
int n,m,a[500005],sum[500005],p[4000005],tot,V,c[4000005],P[4000005],ans[4000005];
struct Node{
	int l,r;
}b[500005];
void update(int p,int d){
	for (;p<=V;p+=p&-p) c[p]+=d;
}
void update2(int p,int d){
	for (;p<=V;p+=p&-p) ans[p]+=d;
}
int query(int x){
	int res=0;
	for (;x;x-=x&-x) res+=c[x];
	return res;
}
int query2(int x){
	int res=0;
	for (;x;x-=x&-x) res+=ans[x];
	return res;
}
int find(int x){
	return lower_bound(p+1,p+V+1,x)-p;
}
int main(){
	scanf("%d%d",&m,&n);
	p[++tot]=1,p[++tot]=m+1;
	for (int i=1;i<=n;i++){
		scanf("%d",&sum[i]),sum[i]+=sum[i-1];
		int x=0;
		for (int j=sum[i-1]+1;j<=sum[i];j++) scanf("%d",&a[j]),x+=a[j];
		int xx=0;
		for (int j=sum[i-1];j<=sum[i];j++){
			p[++tot]=xx+1,p[++tot]=m-(x-xx)+1;
			xx+=a[j+1];
		}
	}
	sort(p+1,p+tot+1);
	V=unique(p+1,p+tot+1)-p-1;
	for (int i=1;i<=n;i++){
		int x=0;
		for (int j=sum[i-1]+1;j<=sum[i];j++) x+=a[j];
		int xx=0;
		tot=0;
		P[++tot]=1,P[++tot]=m+1;
		for (int j=sum[i-1];j<=sum[i];j++){
			update(find(1),1),update(find(xx+1),-1);
			update(find(m-(x-xx)+1),1),update(find(m+1),-1);
			P[++tot]=xx+1,P[++tot]=m-(x-xx)+1;
			xx+=a[j+1];
		}
		sort(P+1,P+tot+1);
		int v=unique(P+1,P+tot+1)-P-1;
		for (int j=1;j<=v;j++) if (query(find(P[j]))==sum[i]-sum[i-1]+1) update2(find(P[j]),1),update2(find(P[j+1]),-1);
		xx=0;
		for (int j=sum[i-1];j<=sum[i];j++){
			update(find(1),-1),update(find(xx+1),1);
			update(find(m-(x-xx)+1),-1),update(find(m+1),1);
			xx+=a[j+1];
		}
	}
	int ans=0;
	for (int i=1;i<=V;i++) if (query2(i)) ans+=p[i+1]-p[i];
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d%d",&m,&n);
      |         ~~~~~^~~~~~~~~~~~~~
lasers.cpp:30:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |                 scanf("%d",&sum[i]),sum[i]+=sum[i-1];
      |                 ~~~~~^~~~~~~~~~~~~~
lasers.cpp:32:59: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |                 for (int j=sum[i-1]+1;j<=sum[i];j++) scanf("%d",&a[j]),x+=a[j];
      |                                                      ~~~~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13