Submission #859864

#	Time	Username	Problem	Language	Result	Execution time	Memory
859864		HoriaHaivas	Sum Zero (RMI20_sumzero)	C++14	61 / 100	853 ms	24520 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;

///extraordinara problema, nu mai vreau

///stau ca prostu sa ma chinui cand pe alte siteuri e limita de memori 1000mb

struct secv
{
    int l;
    int r;
};

struct pls
{
    int val;
    int poz;
};

bool cmp2 (secv a, secv b)
{
    return a.l<b.l;
}

bool cmp (pls a, pls b)
{
    return a.val<b.val;
}

bool cmp3 (pls a, pls b)
{
    return a.poz<b.poz;
}

pls sume[400005];
vector<secv> perechi;
int up[6][400005];
int firstseq[400005];
int pw[6];

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,meh;
    long long sp,least;
    cin >> n;
    sp=0;
    cnt=0;
    for (j=1; j<=n; j++)
    {
        cin >> firstseq[j];
        sume[j].val=sume[j-1].val+firstseq[j];
        sume[j].poz=j;
    }
    sume[0].val=0;
    sume[j].poz=0;
    sort(sume+1,sume+1+n,cmp);
    meh=-1;
    for (j=1; j<=n; j++)
    {
        if (j==1 || sume[j].val!=least)
            meh++;
        least=sume[j].val;
        if (sume[j].val==0)
            sume[0].val=meh;
        sume[j].val=meh;
        firstseq[j]=0;
    }
    sort(sume+1,sume+1+n,cmp3);
    perechi.push_back({0,0});
    for (j=1; j<=n; j++)
    {
        if (sume[j].val==sume[0].val)
        {
            perechi.push_back({firstseq[sume[j].val]+1,j});
        }
        else
        {
            if (firstseq[sume[j].val]!=0)
            {
                perechi.push_back({firstseq[sume[j].val]+1,j});
            }
        }
        firstseq[sume[j].val]=j;
    }
    sort(perechi.begin(),perechi.end(),cmp2);
    cnt=perechi.size()-1;
    it=cnt;
    best=0;
    for (j=n; j>=1; j--)
    {
        if (perechi[it].l==j)
        {
            if (perechi[it].r<perechi[best].r || it==cnt)
            {
                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<=5; j++)
    {
        pw[j]=pw[j-1]*10;
    }
    perechi[0].l=n+1;
    perechi[0].r=n+1;
    ///you ve seen it first here
    for (j=1; j<=5; 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][up[j-1][up[j-1][up[j-1][i]]]]]]]]]];
        }
    }
    cin >> q;
    for (j=1; j<=q; j++)
    {
        cin >> a >> b;
        r=0;
        pas=5;
        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;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:56:17: warning: unused variable 'k' [-Wunused-variable]
   56 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt,meh;
      |                 ^
sumzero.cpp:56:31: warning: unused variable 'mi' [-Wunused-variable]
   56 |     int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas,node,nxt,meh;
      |                               ^~
sumzero.cpp:57:15: warning: variable 'sp' set but not used [-Wunused-but-set-variable]
   57 |     long long sp,least;
      |               ^~

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