Expert.
Put your skills to the test.

Problem summary

Count pairs of equal contiguous length-K windows, one from each of two integer sequences. Only windows whose elements are strictly increasing (W=1), or all equal (W=2), are eligible. Occurrences at different start positions count separately.

Constraints

2 < N,M ≤ 100,000; 1 < K ≤ 10,000; 0 ≤ Ai,Bi ≤ 2,000,000; W∈{1,2}.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

1 2
6
2 1 3 4 3 6
6
3 6 1 3 6 7

3

Solution analysis

1. Count the length of the current strictly increasing or constant run while scanning each sequence. A window ending at a position is eligible exactly when this run length is at least K. We still need an exact, efficient identity for each eligible window, including repeated occurrences.
2. Concatenate the sequences and rank all length-1 blocks by value. Repeatedly double the block length, sorting positions by the pair of ranks of their two halves and assigning equal pairs equal new ranks. Continue until h, the largest power of two at most K. A length-K window is identified by the pair (rank[start],rank[start+K−h]): its first and last h-blocks cover the entire window because 2h≥K. This gives deterministic equality without probabilistic hashing.
3. Collect the keys of eligible A and B windows, sort them, and for each equal-key group add countA·countB. In the sample, A has eligible windows (1,3),(3,4),(3,6), while B has (3,6),(1,3),(3,6),(6,7). The groups contribute one and two, totaling three.

Why it works

Inductively, doubled ranks are equal exactly when the represented blocks are equal, because both halves must agree. Two valid length-K windows agree exactly when both their first and last h-blocks agree: these blocks cover all K positions, and agreement of full windows implies agreement of the blocks. The run test recognizes precisely the requested window variant. Equal-key grouping then counts every eligible cross-sequence occurrence pair once through its unique key.

Watch out. Use 64-bit pair counts. K may exceed a sequence length, giving no windows there. Do not confuse contiguous windows with arbitrary subsequences. Same-value windows at different starts are separate occurrences.

An independently written complete program with standard headers.

// Key idea: Inductively, doubled ranks are equal exactly when the represented blocks are equal,
// because both halves must agree. Two valid length-K windows agree exactly when both their first and
// last h-blocks agree: these blocks cover all K positions, and agreement of full windows implies
// agreement of the blocks.
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int variant,k,n,m;
    cin>>variant>>k>>n;
    vector<int>a(n);
    for(int&x:a){
        cin>>x;
    }
    cin>>m;
    vector<int>b(m),values=a;
    for(int&x:b){
        cin>>x;
    }
    values.insert(values.end(),b.begin(),b.end());
    int length=n+m;
    vector<int>rank=values,nextRank(length),order(length);
    iota(order.begin(),order.end(),0);
    int block=1;
    while(block*2<=k){
        auto key=[&](int i){
            return pair<int,int>{rank[i],i+block<length?rank[i+block]:-1};
        };
        sort(order.begin(),order.end(),[&](int i,int j){
            return key(i)<key(j);
        });
        int currentRank=0;
        nextRank[order[0]]=0;
        for(int i=1;i<length;++i){
            if(key(order[i-1])!=key(order[i])){
                ++currentRank;
            }
            nextRank[order[i]]=currentRank;
        }
        rank.swap(nextRank);
        block*=2;
    }
    vector<pair<pair<int,int>,int>>windows;
    auto collect=[&](const vector<int>&sequence,int offset,int origin){
        int run=0;
        for(int i=0;i<int(sequence.size());++i){
            bool extends=
                i>0&&(variant==1?sequence[i-1]<sequence[i]:sequence[i-1]==sequence[i]);
            run=extends?run+1:1;
            if(run>=k){
                int start=offset+i-k+1;
                windows.push_back({{rank[start],rank[start+k-block]},origin});
            }
        }
    };
    collect(a,0,0);
    collect(b,n,1);
    sort(windows.begin(),windows.end());
    long long answer=0;
    for(int i=0;i<int(windows.size());){
        int j=i;
        long long counts[2]={0,0};
        while(j<int(windows.size())&&windows[j].first==windows[i].first){
            ++counts[windows[j].second];
            ++j;
        }
        answer+=counts[0]*counts[1];
        i=j;
    }
    cout<<answer<<'\n';
}