Submission #421359

#	Time	Username	Problem	Language	Result	Execution time	Memory
421359		Focutai	Sum Zero (RMI20_sumzero)	C++17	61 / 100	592 ms	55836 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 400005
int a[N],pre[N],to[N],n,Q;
vector<signed> st[20];
map<int,int> vis;
signed main()
{
//	cout<<sizeof(st)/1024.0/1024.0<<endl;
	cin>>n;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
	for(int i=n;i>=1;i--)
	{
		vis[pre[i]]=i+1;
		if(!vis[pre[i-1]]) to[i]=n+2;
		else to[i]=vis[pre[i-1]];
	}
	to[n+1]=n+2,to[n+2]=n+2;
	for(int i=n;i>=0;i--) to[i]=min(to[i],to[i+1]);
	for(int i=0;i<=19;i++)
	{
//		printf("^ %d %d\n",i,max(0LL,n-(1<<i)+6));
		st[i].resize(max(0LL,n-(1<<i)+6));
	}
	for(int i=1;i<=n+2;i++) st[0][i]=to[i];
	for(int i=1;i<=19;i++) for(int j=1;j+(1<<i)-1<=n+2;j++)
	{
//		printf("^ %d %d - %d\n",i,j,st[i][j]);
		if(st[i-1][j]+(1<<(i-1))<=n+2) st[i][j]=st[i-1][st[i-1][j]];
		else st[i][j]=n+2;
	}
	cin>>Q;
	while(Q--)
	{
		int l=read(),r=read()+1,ans=0;
		for(int i=19;i>=0;i--) if(l+(1<<i)<=r&&st[i][l]<=r) l=st[i][l],ans+=1<<i;
		printf("%lld\n",ans);
	}
	return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'void print(std::vector<long long int>)':
sumzero.cpp:23:69: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wformat=]
   23 | void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
      |                                                                    ~^
      |                                                                     |
      |                                                                     int
      |                                                                    %lld

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39