QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#871197#8618. Have You Seen This Subarray?ucup-team3734#WA 0ms4064kbC++235.1kb2025-01-25 19:50:082025-01-25 19:50:08

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 19:50:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4064kb
  • [2025-01-25 19:50:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
typedef unsigned long long u64;
typedef double lf;

const int inf = 1e9;
const int BUBEN = 100;


struct state {
	int len, link;
	map<int,int> next;
    int can_reach;
};

vector<state> st;
int sz, last;

void init() {
    st.resize(1);
    sz = last = 0;
	st[0].len = 0;
	st[0].link = -1;
    st[0].can_reach = inf;
	++sz;
}

void addchar(int c, int val) {
    // cerr << "addchar " << c << endl;
    st.push_back({.len = 0, .link = 0, .next = {}, .can_reach = val});
	int cur = sz++;
	st[cur].len = st[last].len + 1;
	int p;
	for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
		st[p].next[c] = cur;
	if (p == -1)
		st[cur].link = 0;
	else {
		int q = st[p].next[c];
		if (st[p].len + 1 == st[q].len)
			st[cur].link = q;
		else {
            st.push_back({.len = 0, .link = 0, .next = {}, .can_reach = val});
			int clone = sz++;
			st[clone].len = st[p].len + 1;
			st[clone].next = st[q].next;
			st[clone].link = st[q].link;
			for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
				st[p].next[c] = clone;
			st[q].link = st[cur].link = clone;
		}
	}
	last = cur;
}


int n, m, q;
vector<int> perm;

int dfs(int v) {
    if (st[v].can_reach != inf) {
        return st[v].can_reach;
    }
    for (const auto &[c, to] : st[v].next) {
        st[v].can_reach = min(st[v].can_reach, dfs(to));
    }
    return st[v].can_reach;
}

void solve_suf() {
    perm.assign(n, 0);
    iota(perm.begin(), perm.end(), 0);
    
    init();
    for (int j = 0; j < n; ++j) {
        addchar(perm[j], inf);
    }
    addchar(-1, 0);
    
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        swap(perm[l], perm[r]);
        for (int j = 0; j < n; ++j) {
            addchar(perm[j], inf);
        }
        addchar(-1, i + 1);
        st[last].can_reach = min(st[last].can_reach, i + 1);
    }
    dfs(0);
    for (int it = 0; it < q; ++it) {
        int k;
        cin >> k;
        vector<int> a(k);
        for (int j = 0; j < k; ++j) {
            cin >> a[j];
            --a[j];
        }
        int v = 0;
        for (int j = 0; j < k; ++j) {
            v = st[v].next[a[j]];
            // cerr << "go " << a[j] << " -> " << v << endl;
        }
        cout << st[v].can_reach << '\n';
    }
}

map<pair<int, int>, int> start_seg;
map<pair<int, int>, vector<pair<int, int>>> segs;

vector<pair<int, int>> intersect(const vector<pair<int, int>> &a, const vector<pair<int, int>> &b) {
    vector<pair<int, int>> res;
    int i = 0, j = 0, jr = (int) b.size();
    if (a.size() == 1 && b.size() > 8) {
        j = (int) (lower_bound(b.begin(), b.end(), make_pair(a[0].first, -1)) - b.begin());
        jr = (int) (lower_bound(b.begin(), b.end(), make_pair(a[0].second, -1)) - b.begin());
    }
    while (i < (int) a.size() && j < jr) {
        int l = max(a[i].first, b[j].first);
        int r = min(a[i].second, b[j].second);
        if (l < r) {
            res.push_back({l, r});
        }
        if (a[i].second < b[j].second) {
            ++i;
        } else {
            ++j;
        }
    }
    return res;
}

void solve() {
    cin >> n >> m >> q;
    if (n <= BUBEN) {
        solve_suf();
        return;
    }
    perm.assign(n, 0);
    iota(perm.begin(), perm.end(), 0);

    for (int i = 0; i + 1 < n; ++i) {
        start_seg[{i, i + 1}] = 0;
    }
    auto close_seg = [](int a, int b, int tm) {
        auto it = start_seg.find({a, b});
        if (it == start_seg.end()) {
            return;
        }
        segs[{a, b}].push_back({it->second, tm});
        start_seg.erase(it);
    };
    auto open_seg = [&](int a, int b, int tm) {
        start_seg[{a, b}] = tm;
    };
    auto close_pos = [&](int x, int tm) {
        if (x > 0) {
            close_seg(perm[x - 1], perm[x], tm);
        }
        if (x + 1 < n) {
            close_seg(perm[x], perm[x + 1], tm);
        }
    };
    auto open_pos = [&](int x, int tm) {
        if (x > 0) {
            open_seg(perm[x - 1], perm[x], tm);
        }
        if (x + 1 < n) {
            open_seg(perm[x], perm[x + 1], tm);
        }
    };
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
    
        close_pos(l, i + 1);
        close_pos(r, i + 1);
        swap(perm[l], perm[r]);
        open_pos(l, i + 1);
        open_pos(r, i + 1);
    }
    for (int i = 0; i < n; ++i) {
        close_pos(i, m + 1);
    }
    for (int it = 0; it < q; ++it) {
        int k;
        cin >> k;
        vector<int> a(k);
        for (int j = 0; j < k; ++j) {
            cin >> a[j];
            --a[j];
        }
        vector<pair<int, int>> cur = {{0, m + 1}};
        for (int j = 0; j + 1 < k; ++j) {
            const auto &qq = segs[{a[j], a[j + 1]}];
            cur = intersect(cur, qq);
        }
        cout << cur[0].first << '\n';
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

input:

6 3 5
1 5
3 4
1 6
2 4 1
3 3 1 5
3 3 4 5
4 5 2 4 3
2 6 2

output:

1
3
0
2
3

result:

ok 5 number(s): "1 3 0 2 3"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 4064kb

input:

50 50 16
21 30
14 39
5 32
31 48
38 50
40 49
14 33
32 42
7 15
5 25
24 28
8 10
18 24
5 39
4 37
9 28
29 39
2 35
11 32
48 49
12 17
38 44
26 33
12 40
19 49
40 41
17 18
20 30
11 15
21 36
37 38
7 48
17 21
8 38
30 34
3 31
7 12
31 47
2 37
20 41
13 40
33 39
10 49
19 40
12 30
23 28
9 45
27 32
4 37
27 29
2 44 4...

output:

2
29
45
24
23
18
1
37
3
16
1
16
2
13
2
2

result:

wrong answer 1st numbers differ - expected: '0', found: '2'