QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#743479 | #8170. $N^a (\log N)^b$ | ucup-team3215# | WA | 8ms | 10860kb | C++23 | 3.2kb | 2024-11-13 19:19:01 | 2024-11-13 19:19:02 |
Judging History
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'