Submission #167671

#	Time	Username	Problem	Language	Result	Execution time	Memory
167671		ngkan146	Matching (CEOI11_mat)	C++11	100 / 100	889 ms	36672 KiB

mat

// old code


#include <bits/stdc++.h>
using namespace std;
struct fwTree{
    int node[1000005];
    void clear(){
        for(int i=1;i<=(int)1e6;i++)
            node[i] = 0;
    }
    void upd(int pos,int val){
        for(;pos<=(int)1e6;pos+=pos&-pos)
            node[pos] += val;
    }
    int get(int pos){
        int res = 0;
        for(;pos;pos-=pos&-pos)
            res += node[pos];
        return res;
    }
};
int getInt(){
    char c;
    int res = 0;
    bool mark = 0;
    while(c = getchar()){
        if (c < '0' || '9' < c){
            if (mark)   break;
            continue;
        }
        mark = 1;
        res = res * 10 + (c - '0');
    }
    return res;
}

int n, m, a[2000005];
int val[1000005];
int prefixSuffix[2000005];
fwTree fw;
vector <int> nen;
int main(){
    // input
    n = getInt();
    m = getInt();

    for(int i=1;i<=n;i++)
        a[getInt()] = i;
    for(int i=1;i<=m;i++)
        a[n+1+i] = getInt(),
        nen.push_back(a[n+1+i]);

    sort(nen.begin(), nen.end());
    for(int i=1;i<=m;i++)
        a[n+1+i] = lower_bound(nen.begin(), nen.end(), a[n+1+i]) + 1 - nen.begin();// cout << a[i+1+n] << ' '; cout << endl;

    // val[i] = how many columns that are lower than column i when we consider only first i columns
    for(int i=1;i<=n;i++){
        val[i] = fw.get(a[i]);
        fw.upd(a[i], 1);
    }

    // prefixSuffix[i] = longest suffix at i that equals to prefix

    fw.clear();
    int pivot = 2;

    vector <int> res;
    //cout << 0 << ' ';
    for(int i=2;i<=n+m+1;i++){
        if (i == n+1){
            fw.clear();
            prefixSuffix[i] = 0;
            pivot = i+1;
            //cout << 0 << ' ';
            continue;
        }
        int tmp = prefixSuffix[i-1];
        if (tmp == n){
            while(pivot < i - prefixSuffix[tmp])
                fw.upd(a[pivot], -1),
                ++ pivot;
            tmp = prefixSuffix[tmp];
        }

        while(fw.get(a[i]) != val[tmp+1]){
            while(pivot < i - prefixSuffix[tmp])
                fw.upd(a[pivot], -1),
                ++ pivot;
            tmp = prefixSuffix[tmp];
        }
        fw.upd(a[i], 1);
        prefixSuffix[i] = tmp + 1;
        //cout << prefixSuffix[i] << ' ';
        if (i > n && prefixSuffix[i] == n)
            res.push_back(i - n - 1 - n + 1);
    }
    //cout << endl;
    printf("%d\n",res.size());
    for(auto v: res)    printf("%d ", v);
}

Compilation message (stderr)

mat.cpp: In function 'int getInt()':
mat.cpp:27:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
     while(c = getchar()){
           ~~^~~~~~~~~~~
mat.cpp: In function 'int main()':
mat.cpp:100:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",res.size());
                   ~~~~~~~~~~^

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10