제출 #421408

#제출 시각아이디문제언어결과실행 시간메모리
421408FocutaiSum Zero (RMI20_sumzero)C++17
61 / 100
329 ms35920 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 n,Q; struct Edge{signed v,nxt;}; Edge edge[N]; signed fir[N],ss; void add(int u,int v) {edge[++ss]=(Edge){v,fir[u]},fir[u]=ss;} map<int,int> vis; signed dep[N],siz[N],son[N],fa[N],top[N],dfn[N],id[N],dfscnt; void dfs1(int u,int f) { fa[u]=f,dep[u]=dep[f]+1,siz[u]=1; for(int i=fir[u];i!=0;i=edge[i].nxt) { int v=edge[i].v; dfs1(v,u),siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp) { top[u]=tp,dfn[u]=++dfscnt,id[dfscnt]=u; if(son[u]) dfs2(son[u],tp); for(int i=fir[u];i!=0;i=edge[i].nxt) { int v=edge[i].v; if(v!=son[u]) dfs2(v,v); } } signed main() { cin>>n; for(int i=1;i<=n;i++) dep[i]=read(); for(int i=1;i<=n;i++) pre[i]=pre[i-1]+dep[i]; for(int i=n;i>=1;i--) { vis[pre[i]]=i+1; if(!vis[pre[i-1]]) top[i]=n+2; else top[i]=vis[pre[i-1]]; } vis.clear(); top[n+1]=n+2,top[n+2]=n+2; for(int i=n;i>=1;i--) top[i]=min(top[i],top[i+1]); for(int i=1;i<=n+1;i++) add(top[i],i); dfs1(n+2,n+2),dfs2(n+2,n+2); // for(int i=1;i<=n+2;i++) print(G[i]); // for(int i=1;i<n+2;i++) printf("%d %d\n",i,fa[i]); // for(int i=1;i<=n+2;i++) printf("%d%c",id[i]," \n"[i==n+2]); cin>>Q; while(Q--) { int l=read(),r=read()+1,ans=0; while(fa[top[l]]<=r) ans+=dep[l]-dep[top[l]]+1,l=fa[top[l]]; // printf("^ %d %d\n",l,ans); int R=dfn[l],L=dfn[top[l]],res=0; // printf("%d %d\n",L,R); while(L<=R) { int mid=(L+R)/2; if(id[mid]<=r) R=mid-1,res=dfn[l]-mid; else L=mid+1; } printf("%lld\n",ans+res); } return 0; } /* 10 5 5 -1 4 -5 -4 -4 4 -4 0 1 1 10 */

컴파일 시 표준 에러 (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 'void add(long long int, long long int)':
sumzero.cpp:30:42: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
   30 | void add(int u,int v) {edge[++ss]=(Edge){v,fir[u]},fir[u]=ss;}
      |                                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...