제출 #859551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859551		HoriaHaivas	Sum Zero (RMI20_sumzero)	C++14	61 / 100	204 ms	14348 KiB

sumzero

/*
    "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;
    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<=cnt;j++)
    {
         up[0][j]=firstseq[perechi[j].r+1];
    }
    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;
        pas=16;
        node = firstseq[a];
        while (pas>=0)
        {
            nxt=up[pas][node];
            if (perechi[nxt].nodeval!=0 && perechi[nxt].r<=b)
            {
                r+=(1<<pas);
                node=nxt;
            }
            pas--;
        }
        if (perechi[node].nodeval!=0 && perechi[node].r<=b)
        cout << r+1 << "\n";
        else
        cout << 0 << "\n";
    }
    return 0;
}

컴파일 시 표준 에러 (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;
      |                               ^~

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