Submission #859528

#TimeUsernameProblemLanguageResultExecution timeMemory
859528HoriaHaivasSum Zero (RMI20_sumzero)C++14
22 / 100
1060 ms13296 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; int nodeval; }; struct cmp { bool operator()(secv a, secv b) { return a.r>b.r; } }; bool cmp2 (secv a, secv b) { return a.l<b.l; } int v[100005]; long long sp[100005]; map<long long,int> last; priority_queue<secv,vector<secv>,cmp> pq; secv perechi[100005]; int up[17][100005]; int firstseq[100005]; secv jumpto(int node, int steps) { //debug(node); //debug(steps); int i,j; for (j=0; j<=16; j++) { if (steps&(1<<j)) node=up[j][node]; } //debug(node); return perechi[node]; } 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; cin >> n; for (j=1; j<=n; j++) { cin >> v[j]; sp[j]=sp[j-1]+v[j]; } cnt=0; for (j=1; j<=n; j++) { if (sp[j]==0) { cnt++; perechi[cnt].l=last[sp[j]]+1; perechi[cnt].r=j; } else { if (last[sp[j]]!=0) { cnt++; perechi[cnt].l=last[sp[j]]+1; perechi[cnt].r=j; } } last[sp[j]]=j; } sort(perechi+1,perechi+1+cnt,cmp2); for (j=1; j<=cnt; j++) perechi[j].nodeval=j; for (j=1; j<=cnt; j++) { /* debug(perechi[j].l); debug(perechi[j].r); cerr << "\n"; */ if (!pq.empty() && pq.top().r<perechi[j].l) { while (!pq.empty() && pq.top().r<perechi[j].l) { up[0][pq.top().nodeval]=perechi[j].nodeval; pq.pop(); } } pq.push(perechi[j]); /* debug(pq.top().l); debug(pq.top().r); */ } while (!pq.empty()) { up[0][pq.top().nodeval]=0; pq.pop(); } perechi[0].l=n+1; perechi[0].r=n+1; perechi[0].nodeval=0; 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<=16; j++) { for (i=1; i<=cnt; i++) { up[j][i]=up[j-1][up[j-1][i]]; } } cin >> q; for (j=1; j<=q; j++) { cin >> a >> b; r=0; for (i=a;i<=b;i++) { if (perechi[firstseq[a]].r<=b) r++; a=perechi[firstseq[a]].r+1; } cout << r << "\n"; } return 0; }

Compilation message (stderr)

sumzero.cpp: In function 'secv jumpto(int, int)':
sumzero.cpp:44:9: warning: unused variable 'i' [-Wunused-variable]
   44 |     int i,j;
      |         ^
sumzero.cpp: In function 'int main()':
sumzero.cpp:61:17: warning: unused variable 'k' [-Wunused-variable]
   61 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt;
      |                 ^
sumzero.cpp:61:31: warning: unused variable 'mi' [-Wunused-variable]
   61 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt;
      |                               ^~
sumzero.cpp:61:40: warning: unused variable 'pas' [-Wunused-variable]
   61 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt;
      |                                        ^~~
sumzero.cpp:61:44: warning: unused variable 'node' [-Wunused-variable]
   61 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt;
      |                                            ^~~~
sumzero.cpp:61:49: warning: unused variable 'nxt' [-Wunused-variable]
   61 |     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...