제출 #859844

#제출 시각아이디문제언어결과실행 시간메모리
859844HoriaHaivasSum Zero (RMI20_sumzero)C++14
22 / 100
195 ms21356 KiB
/* "care a facut teste cu Lattice reduction attack e ciudat" - 2023 - */ #include<bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #pragma GCC optimize("Ofast") using namespace std; struct secv { int l; int r; }; bool cmp2 (secv a, secv b) { return a.l<b.l; } map<long long,int> last; secv perechi[400005]; int up[8][400005]; int firstseq[400005]; int pw[8]; int main() { ifstream fin("secvp.in"); ofstream fout("secvp.out"); ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt; long long sp; cin >> n; sp=0; cnt=0; for (j=1; j<=n; j++) { cin >> firstseq[j]; sp=sp+firstseq[j]; if (sp==0) { cnt++; perechi[cnt].l=last[sp]+1; perechi[cnt].r=j; } else { if (last[sp]!=0) { cnt++; perechi[cnt].l=last[sp]+1; perechi[cnt].r=j; } } last[sp]=j; } sort(perechi+1,perechi+1+cnt,cmp2); perechi[0].l=n+1; perechi[0].r=n+1; it=cnt; best=0; for (j=n; j>=1; j--) { if (perechi[it].l==j) { if (perechi[it].r<perechi[best].r) { best=it; } it--; } firstseq[j]=best; /* debugs(j); debug(firstseq[j]); */ } for (j=1; j<=cnt; j++) { up[0][j]=firstseq[perechi[j].r+1]; } pw[0]=1; for (j=1; j<=7; j++) { pw[j]=pw[j-1]*7; } ///you ve seen it here first for (j=1; j<=7; j++) { for (i=1; i<=cnt; i++) { up[j][i]=up[j-1][up[j-1][up[j-1][up[j-1][up[j-1][up[j-1][up[j-1][i]]]]]]]; } } cin >> q; for (j=1; j<=q; j++) { cin >> a >> b; r=0; pas=7; node=firstseq[a]; while (pas>=0) { /* nxt=up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][node]]]]]]]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*9; node=nxt; } else { nxt=up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][node]]]]]]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*8; node=nxt; } else { nxt=up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][node]]]]]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*7; node=nxt; } else { */ nxt=up[pas][up[pas][up[pas][up[pas][up[pas][up[pas][node]]]]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*6; node=nxt; } else { nxt=up[pas][up[pas][up[pas][up[pas][up[pas][node]]]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*5; node=nxt; } else { nxt=up[pas][up[pas][up[pas][up[pas][node]]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*4; node=nxt; } else { nxt=up[pas][up[pas][up[pas][node]]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*3; node=nxt; } else { nxt=up[pas][up[pas][node]]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]*2; node=nxt; } else { nxt=up[pas][node]; if (nxt!=0 && perechi[nxt].r<=b) { r+=pw[pas]; node=nxt; } } } } } } //} // } //} pas--; } if (node!=0 && perechi[node].r<=b) cout << r+1 << "\n"; else cout << 0 << "\n"; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'int main()':
sumzero.cpp:36:17: warning: unused variable 'k' [-Wunused-variable]
   36 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt;
      |                 ^
sumzero.cpp:36:31: warning: unused variable 'mi' [-Wunused-variable]
   36 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt;
      |                               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...