QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#743479#8170. $N^a (\log N)^b$ucup-team3215#WA 8ms10860kbC++233.2kb2024-11-13 19:19:012024-11-13 19:19:02

Judging History

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

  • [2024-11-13 19:19:02]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:10860kb
  • [2024-11-13 19:19:01]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
using ll = long long;
using vl = vector<ll>;
using pll = array<ll, 2>;

const int LOG = 1;
const int N = 2;
const int OP = 3;
struct token {
    int type;
    pll val;
};
const ll INF = 1e18;

template<class T>
struct segtree {
    vector<T> tr;
    int n;

    segtree(int n) : n(n), tr(4 * n) {}

    void set(int p, T x) {
        set(0, 0, n, p, x);
    }

    T f(T a, T b) {
        return a < b ? a : b;
    }

    void set(int id, int lo, int hi, int p, T x) {
        if (lo + 1 == hi) {
            tr[id] = x;
            return;
        }
        int mid = (lo + hi) / 2;
        if (p < mid) set(id * 2 + 1, lo, mid, p, x);
        else set(id * 2 + 2, mid, hi, p, x);
        tr[id] = f(tr[id * 2 + 1], tr[id * 2 + 2]);
    }

    T get(int l, int r) {
        return get(0, 0, n, l, r);
    }

    T get(int id, int lo, int hi, int l, int r) {
        if (r <= lo || hi <= l) return {INF, INF, INF};
        if (l <= lo && hi <= r) return tr[id];
        int mid = (lo + hi) / 2;
        return f(get(id * 2 + 1, lo, mid, l, r), get(id * 2 + 2, mid, hi, l, r));
    }
};

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

    array<int, 128> prior;
    prior['*'] = 2;
    prior['+'] = 1;
    string s;
    cin >> s;
    vector<token> v;
    ll num = 0, cnt = 0, logcnt = -1;
    int tp = 0;
    char last;
    auto add = [&](char c = 0) {
        if (logcnt != -1 || tp == -1) return;
        if (tp == LOG) v.push_back({LOG, {0, max(1ll, num)}}), tp = -1;
        if (tp == N) v.push_back({N, {max(1ll, num), 0}}), tp = -1;
        if (tp == OP) v.push_back({OP, {cnt, prior[c]}}), tp = -1;
    };
    for (char c : s) {
        if (c == '(') {
            add();
            ++cnt;
        } else if (c == ')') {
            add();
            --cnt;
            if (cnt == logcnt) {
                logcnt = -1;
                tp = LOG, num = 0;
            }
        } else if (c == 'N') {
            num = 0;
            tp = N;
        } else if (c == 'l' || c == 'o' || c == 'g') {
            num = 0;
            tp = LOG;
            logcnt = cnt;
        } else if (c == '+' || c == '*') {
            add();
            tp = OP;
            add(c);
        } else if ('0' <= c && c <= '9') {
            num = num * 10 + c - '0';
        }
        last = c;
    }
    // for (auto [x, y] : v) {
    //     cout << x << ' ' << y[0] << ' ' << y[1] << endl;
    // }
    // return 0;
    int m = v.size();
    using ar3 = array<ll, 3>;
    segtree<ar3> st(m);
    for (int i = 0; i < m; ++i) {
        if (v[i].type == OP) st.set(i, {v[i].val[0], v[i].val[1], i});
        else st.set(i, {INF, INF, INF});
    }
    auto dfs = [&](int lo, int hi, auto && dfs) -> pll {
        if (lo + 1 >= hi) return v[lo].val;
        auto [_, __, id] = st.get(lo, hi);
        pll l = dfs(lo, id, dfs), r = dfs(id + 1, hi, dfs);
        if (v[id].val[1] == prior['+']) {
            return l > r ? l : r;
        } else {
            l[0] += r[0], l[1] += r[1];
            return l;
        }
    };
    pll ans = dfs(0, m, dfs);
    cout << ans[0] << ' ' << ans[1] << endl;
}

详细

Test #1:

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

input:

N*log(N^2)*log(N)+N+log(N^1+N)^2*N

output:

1 2

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

N*log(log(N))

output:

1 1

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

(((N))*N^234567890+N^2)

output:

234567891 0

result:

ok 2 tokens

Test #4:

score: 0
Accepted
time: 8ms
memory: 10860kb

input:

log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)+log(N)...

output:

0 1

result:

ok 2 tokens

Test #5:

score: -100
Wrong Answer
time: 7ms
memory: 10812kb

input:

log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)*log(N)...

output:

0 14284

result:

wrong answer 2nd words differ - expected: '14285', found: '14284'