QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116779#5150. Alternating Algorithmbatrr#WA 3ms37712kbC++233.7kb2023-06-30 04:04:182023-06-30 04:04:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 04:04:21]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:37712kb
  • [2023-06-30 04:04:18]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 400500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}

int n, a[N];
int p[N];
int ans;

struct state{
    bool emp;

    int len, s;
    int mx[2];
    state(){
        emp = true;
    }
    state(int pos, int val){
        emp = false;
        len = 1;
        s = 0;
        for(int i = 0; i < 2; i++)
            mx[i] = -inf;
        if(val == 0)
            val = -2;
        else
            val = 1;
        if(val == -2)
            mx[pos & 1] = max(mx[pos & 1], val);
        s += val;
    }
    int calc(){
        int res = -inf;
        res = max(res, mx[0] + 1);
        res = max(res, mx[1]);
        return res;
    }
} t[N << 2];
state kek(state a, state b){
    if(a.emp)
        return b;
    if(b.emp)
        return a;
    state c;
    c.emp = false;
    c.len = a.len + b.len;
    c.s = a.s + b.s;
    for(int i = 0; i < 2; i++)
        c.mx[i] = max(a.mx[i], b.mx[i] + a.s);
    return c;
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = state(tl, 1);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
    t[v] = kek(t[v << 1], t[v << 1 | 1]);
}

state get(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l || l > r)
        return state();
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) >> 1;
    return kek(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
}

void upd(int v, int tl, int tr, int p) {
    if (tl == tr) {
        t[v] = state(tl, 0);
        return;
    }
    int tm = (tl + tr) >> 1;
    if (p <= tm)
        upd(v << 1, tl, tm, p);
    else
        upd(v << 1 | 1, tm + 1, tr, p);
    t[v] = kek(t[v << 1], t[v << 1 | 1]);
}

void solve() {
    cin >> n;
    n++;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    iota(p, p + n, 0);
    sort(p, p + n, [](int i, int j) {
        return a[i] < a[j];
    });
    set<int> st0, st1;
    for (int i = 0; i < n; i++)
        st1.insert(i);
    build(1, 0, n - 1);
    for (int i = 0, j = 0; i < n; i = j) {
        while (j < n && a[p[i]] == a[p[j]])
            j++;
        for (int q = i; q < j; q++) {
            st1.erase(p[q]);
            st0.insert(p[q]);
            upd(1, 0, n - 1, p[q]);
        }
        if (st1.empty())
            break;
        int L = *st1.begin();
        int R = *st0.rbegin();
        auto res = get(1, 0, n - 1, L, R);
        ans = max(ans, res.calc() + (int)st0.size() - L);
//        cerr << res.calc() << " " << (int)st0.size() - L << endl;
//        cerr << res.len << " " << res.s << " " << res.mx[0] << " " << res.mx[1] << endl;
    }
    cout << ans + 1 << "\n";
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

詳細信息

Test #1:

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

input:

3
8 13 4 10

output:

3

result:

ok single line: '3'

Test #2:

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

input:

5
13 12 14 10 14 12

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 3ms
memory: 36860kb

input:

2
2 2 1

output:

3

result:

ok single line: '3'

Test #4:

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

input:

1
300172042 474444146

output:

119

result:

wrong answer 1st lines differ - expected: '0', found: '119'