제출 #421365

#제출 시각아이디문제언어결과실행 시간메모리
421365FocutaiSum Zero (RMI20_sumzero)C++17
0 / 100
0 ms204 KiB
#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 pre[N]; signed a[N],to[N],n,Q; vector<signed> st[20]; map<int,int> vis; signed main() { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); // 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]); int sum=0; for(int i=0;i<=11;i++) { // fprintf(stderr,"^ %d %d\n",i,max(0LL,n-(1<<i)+6)); st[i].resize(max(0,n-(1<<i)+6)); st[i].shrink_to_fit(); sum+=st[i].size(); } cerr<<sum*4/1024.0/1024.0<<endl; for(int i=1;i<=n+2;i++) st[0][i]=to[i]; for(int i=1;i<=11;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=11;i>=0;i--) while(l+(1<<i)<=r&&st[i][l]<=r) l=st[i][l],ans+=1<<i; printf("%lld\n",ans); } return 0; }

컴파일 시 표준 에러 (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
sumzero.cpp: In function 'int main()':
sumzero.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen("in.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sumzero.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen("out.txt","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...