oj.uz

Submission #167671

# Submission time Handle Problem Language Result Execution time Memory
167671 2019-12-09T11:15:15 Z ngkan146 Matching (CEOI11_mat) C++11
100 / 100
 889 ms 36672 KB 
// 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4216 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4856 KB Output is correct
2 Correct 14 ms 4728 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4856 KB Output is correct
2 Correct 14 ms 4728 KB Output is correct
3 Correct 7 ms 4344 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8336 KB Output is correct
2 Correct 67 ms 7764 KB Output is correct
3 Correct 127 ms 9068 KB Output is correct
4 Correct 128 ms 9704 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9036 KB Output is correct
2 Correct 114 ms 7888 KB Output is correct
3 Correct 89 ms 9056 KB Output is correct
4 Correct 79 ms 10092 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 9196 KB Output is correct
2 Correct 78 ms 8812 KB Output is correct
3 Correct 101 ms 8808 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 23012 KB Output is correct
2 Correct 889 ms 36672 KB Output is correct
3 Correct 388 ms 18216 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 22676 KB Output is correct
2 Correct 577 ms 22884 KB Output is correct
3 Correct 873 ms 31216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 23732 KB Output is correct
2 Correct 372 ms 33708 KB Output is correct
3 Correct 545 ms 20396 KB Output is correct
4 Correct 566 ms 30940 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 24248 KB Output is correct
2 Correct 542 ms 20740 KB Output is correct
3 Correct 192 ms 15588 KB Output is correct
4 Correct 681 ms 32732 KB Output is correct