Submission #7225615


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define pr pair<int,int>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    #define bin(x) (1ll<<(x))
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):0;}
    const int INF=0x3f3f3f3f;
    const int MOD=998244353;
    inline int mm(const int x){return x>=MOD?x-MOD:x;}
    inline ll qpower(ll x,ll e)
    {
        ll ans=1;
        while(e)
        {
            if(e&1) ans=ans*x%MOD;
            x=x*x%MOD;e>>=1;
        }
        return ans;
    }
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e6+10;

    vc<pr> nw;int L;
    ll calcnw()
    {
        ll ans=0,sum=0;
        for(int t=L-1;t<sz(nw);t++) sum+=nw[t-L+1].FR,ans+=sum*nw[t].SE;
        return ans;
    }
    vc< pair<pr,pr> > all,all2;//(fl,fr,li,ri)表示覆盖区间、作为端点的系数;里面所有数当前都是val
    vc<pr> num;
    void main()
    {
        int n=qread();L=qread();
        for(int i=1;i<=n;i++) num.PB(MP(qread(),i));sort(all(num));
        ll ans=n;int val=0,numpos=0;
        while(1)
        {
            if(!sz(all))
            {
                if(numpos==n) break;
                val=num[numpos].FR;
            } else val++;
            while(numpos<n and num[numpos].FR==val)//newguy
                all.PB(MP( MP(num[numpos].SE,num[numpos].SE),MP(1,1) )),numpos++;
            sort(all(all));all2.clear();
            for(int i=0,j;i<sz(all);i=j+1)
            {
                j=i;while(j+1<sz(all) and all[j].FR.SE+1==all[j+1].FR.FR) j++;//极长连续段
                int cnt=(j-i+1)/L;if(!cnt) continue;
                nw.clear();for(int k=i;k<=j;k++) nw.PB(all[k].SE);ans+=calcnw();
                vc<pr> pos,pp;pp.resize(cnt);
                for(int k=i;k<=j;k++)
                {
                    int tl=k-i+1,tr=j-k+1;
                    if(tl>=L) pp[tl/L-1].SE+=all[k].SE.SE;
                    if(tr>=L) pp[cnt-tr/L].FR+=all[k].SE.FR;
                }
                nw=pp;ans-=calcnw();
                for(int t=0;t<cnt;t++) pos.PB(MP(all[i].FR.FR+t,all[i].FR.FR+t));pos[cnt-1].SE=all[j].FR.SE;
                for(int t=0;t<cnt;t++) all2.PB(MP(pos[t],pp[t]));
            }
            all=all2;
        }
        write(ans);
    }
};
int main()
{
    srand(time(0));
    mine::main();
}

Submission Info

Submission Time
Task F - Counting of Subarrays
User Zory
Language C++14 (GCC 5.4.1)
Score 1800
Code Size 3156 Byte
Status
Exec Time 61 ms
Memory 11372 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample01.txt, sample02.txt, sample03.txt
All 1800 / 1800 sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in50.txt, in51.txt, in52.txt, in53.txt, in54.txt, in55.txt, in56.txt, in57.txt, in58.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt 2 ms 256 KB
in02.txt 2 ms 256 KB
in03.txt 2 ms 256 KB
in04.txt 2 ms 256 KB
in05.txt 2 ms 256 KB
in06.txt 2 ms 256 KB
in07.txt 2 ms 256 KB
in08.txt 1 ms 256 KB
in09.txt 2 ms 256 KB
in10.txt 2 ms 256 KB
in11.txt 2 ms 256 KB
in12.txt 2 ms 256 KB
in13.txt 1 ms 256 KB
in14.txt 2 ms 256 KB
in15.txt 2 ms 256 KB
in16.txt 2 ms 256 KB
in17.txt 2 ms 256 KB
in18.txt 49 ms 2544 KB
in19.txt 44 ms 3312 KB
in20.txt 39 ms 2420 KB
in21.txt 61 ms 3184 KB
in22.txt 43 ms 2544 KB
in23.txt 49 ms 2420 KB
in24.txt 43 ms 2420 KB
in25.txt 31 ms 2420 KB
in26.txt 31 ms 2420 KB
in27.txt 41 ms 3568 KB
in28.txt 27 ms 2420 KB
in29.txt 47 ms 2420 KB
in30.txt 55 ms 2544 KB
in31.txt 47 ms 2544 KB
in32.txt 40 ms 2420 KB
in33.txt 55 ms 2544 KB
in34.txt 52 ms 2420 KB
in35.txt 60 ms 2800 KB
in36.txt 48 ms 2420 KB
in37.txt 50 ms 2420 KB
in38.txt 54 ms 2420 KB
in39.txt 58 ms 2544 KB
in40.txt 57 ms 2544 KB
in41.txt 60 ms 2544 KB
in42.txt 60 ms 2544 KB
in43.txt 52 ms 2420 KB
in44.txt 46 ms 2420 KB
in45.txt 46 ms 2420 KB
in46.txt 42 ms 2420 KB
in47.txt 47 ms 10476 KB
in48.txt 52 ms 6384 KB
in49.txt 56 ms 6640 KB
in50.txt 59 ms 6768 KB
in51.txt 51 ms 11372 KB
in52.txt 54 ms 7024 KB
in53.txt 35 ms 2420 KB
in54.txt 33 ms 2420 KB
in55.txt 40 ms 2420 KB
in56.txt 45 ms 2544 KB
in57.txt 41 ms 2420 KB
in58.txt 54 ms 2672 KB
sample01.txt 1 ms 256 KB
sample02.txt 1 ms 256 KB
sample03.txt 1 ms 256 KB