QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#241705#7147. IQ Test8BQube#WA 2ms13832kbC++202.2kb2023-11-06 16:10:012023-11-06 16:10:01

Judging History

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

  • [2023-11-06 16:10:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13832kb
  • [2023-11-06 16:10:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

int pos[400005], zero[400005], req[400005], bit[800005], ok[400005], dp[400005];
vector<int> val;

void modify(int x, int v) {
    for (; x <= SZ(val); x += x & -x)
        bit[x] = max(bit[x], v);
}

int query(int x) {
    int res = -1;
    for (; x; x -= x & -x)
        res = max(res, bit[x]);
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, tp = 0;

    auto pb = [&](int i) {
        if (i > 0 && (zero[tp] < 0 || zero[tp] > i || req[tp] < 0 || req[tp] >= i)) return;
        pos[tp] = i, dp[tp] = -1;
        val.pb(i - zero[tp]), val.pb(i - req[tp]);
        ++tp;
    };

    zero[tp] = 0, req[tp] = 0;
    pb(0), dp[0] = 0;

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'A') {
            zero[tp] = x + 1, req[tp] = x;
            pb(i);
            zero[tp] = y, req[tp] = y;
            pb(i);
        }
        else {
            zero[tp] = (i - 1 - x) + 1, req[tp] = (i - 1 - x);
            pb(i);
            zero[tp] = (i - 1 - y), req[tp] = (i - 1 - y);
            pb(i);
        }
    }
    vector<int> R(tp), C(tp);
    iota(ALL(R), 0), iota(ALL(C), 0);
    sort(ALL(R), [&](int a, int b) {
        return req[a] < req[b]; 
    });
    sort(ALL(C), [&](int a, int b) {
        return zero[a] < zero[b];
    });
    sort(ALL(val)), val.resize(unique(ALL(val)) - val.begin());
    fill_n(bit, SZ(val) + 1, -1);

    auto get_pos = [&](int x) {
        return upper_bound(ALL(val), x) - val.begin();  
    };

    int p = 0;
    for (int i : R) {
        while (p < SZ(C) && zero[C[p]] <= req[i]) {
            ok[C[p]] = 1;
            if (dp[C[p]] >= 0) modify(get_pos(pos[C[p]] - zero[C[p]]), dp[C[p]]); 
            ++p;
        }
        if (i > 0) {
            dp[i] = query(get_pos(pos[i] - req[i]) - 1);
            if (dp[i] >= 0) ++dp[i];
        }
        if (ok[i])
            modify(get_pos(pos[i] - zero[i]), dp[i]);
    }
    cout << *max_element(dp, dp + tp) << "\n";
}

详细

Test #1:

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

input:

2
A 0 1
B 0 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 13832kb

input:

2
A 1 2
B 0 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 11804kb

input:

1
A 1 1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 1ms
memory: 9736kb

input:

10
A 1 1
A 1 0
B 1 0
B 3 1
B 1 0
B 1 5
A 5 6
B 3 0
A 0 0
B 8 9

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 12020kb

input:

10
A 3 0
B 0 1
B 0 2
A 1 5
B 5 2
B 3 2
B 7 2
A 4 3
B 6 0
B 2 2

output:

5

result:

wrong answer 1st numbers differ - expected: '6', found: '5'