QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116779 | #5150. Alternating Algorithm | batrr# | WA | 3ms | 37712kb | C++23 | 3.7kb | 2023-06-30 04:04:18 | 2023-06-30 04:04:21 |
Judging History
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'