oj.uz

답안 #936933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936933 2024-03-03T04:23:40 Z _callmelucian Matching (CEOI11_mat) C++14
63 / 100
 399 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct pBIT {
    vector<vector<pii>> tr;
    pBIT (int sz) : tr(sz + 1, vector<pii>(1, make_pair(-1, 0))) {}

    int get (int k, int ver) {
        auto it = upper_bound(all(tr[k]), make_pair(ver, INT_MAX));
        return prev(it)->second;
    }

    int p (int k) { return k & -k; }

    void update (int k, int val, int ver) {
        for (; k < tr.size(); k += p(k)) {
            int cur = tr[k].back().second + val;
            tr[k].push_back(make_pair(ver, cur));
        }
    }

    int query (int k, int ver, int ans = 0) {
        for (; k; k -= p(k)) ans += get(k, ver);
        return ans;
    }
};

struct BIT {
    vector<int> tr;
    BIT (int sz) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int k, int val) {
        for (; k < tr.size(); k += p(k))
            tr[k] += val;
    }

    int query (int k, int ans = 0) {
        for (; k; k -= p(k)) ans += tr[k];
        return ans;
    }
};

vector<int> mp;

void compress() {
    sort(all(mp)); filter(mp);
}

int getID (int u) {
    return lower_bound(all(mp), u) - mp.begin() + 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> s(n), h(m);
    for (int i = 1; i <= n; i++) {
        int p; cin >> p;
        s[p - 1] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> h[i];
        mp.push_back(h[i]);
    }
    compress();

    vector<int> vec = s;
    vec.push_back(INT_MAX);
    for (int u : h) vec.push_back(getID(u));

    /* prefix function */
    int sz = vec.size();
    vector<int> pi(sz), pre(sz), ans;

    pBIT tree(max(n, m));
    for (int i = 0; i < sz; i++)
        if (vec[i] < INT_MAX) tree.update(vec[i], 1, i);

    BIT helper(sz);
    for (int i = 0; i < sz; i++) {
        if (vec[i] == INT_MAX) continue;
        helper.update(vec[i], 1); pre[i] = helper.query(vec[i]);
    }

    function<bool(int,int)> same = [&] (int i, int j) {
        // [0..i-1] + i == [j-i..j-1] + j
        if (vec[i] == INT_MAX || vec[j] == INT_MAX) return false;
        return pre[i] == (pre[j] - tree.query(vec[j], j - i - 1));
    };

    for (int i = 1; i < sz; i++) {
        int j = pi[i - 1];
        while (j && !same(j, i)) j = pi[j - 1];
        if (same(j, i)) pi[i] = j + 1;
    }
    /* prefix function */

    for (int i = 0; i < pi.size(); i++)
        if (pi[i] == n) ans.push_back(i - 2 * n + 1);

    cout << ans.size() << "\n";
    for (int u : ans) cout << u << " ";

    return 0;
}

Compilation message

mat.cpp: In member function 'void pBIT::update(int, int, int)':
mat.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (; k < tr.size(); k += p(k)) {
      |                ~~^~~~~~~~~~~
mat.cpp: In member function 'void BIT::update(int, int)':
mat.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (; k < tr.size(); k += p(k))
      |                ~~^~~~~~~~~~~
mat.cpp: In function 'int main()':
mat.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = 0; i < pi.size(); i++)
      |                     ~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 4308 KB Output is correct
2 Correct 18 ms 4048 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 4588 KB Output is correct
2 Correct 17 ms 4468 KB Output is correct
3 Correct 2 ms 860 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 39764 KB Output is correct
2 Correct 145 ms 36528 KB Output is correct
3 Correct 399 ms 47468 KB Output is correct
4 Correct 393 ms 47804 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 45720 KB Output is correct
2 Correct 316 ms 40788 KB Output is correct
3 Correct 182 ms 40548 KB Output is correct
4 Correct 144 ms 40484 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 44248 KB Output is correct
2 Correct 165 ms 44292 KB Output is correct
3 Correct 229 ms 41664 KB Output is correct

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 269 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 250 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 242 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 221 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -