oj.uz

답안 #752335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752335 2023-06-02T21:54:49 Z aryan12 서열 (APIO23_sequence) C++17
0 / 100
 95 ms 6116 KB 
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int N = 5e5 + 5, INF = 1e18;
int seg[N * 2 * 4];

int32_t print_occ(int val, vector<int32_t> &x)
{
    int ans = 0;
    for(int i: x)
    {
        ans += (i == val);
    }
    return ans;
}

void Build(int l, int r, int pos)
{
    seg[pos] = INF;
    if(l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    Build(l, mid, pos * 2);
    Build(mid + 1, r, pos * 2 + 1);
}

void Update(int l, int r, int pos, int qpos, int qval)
{
    if(l == r)
    {
        seg[pos] = min(seg[pos], qval);
        return;
    }
    int mid = (l + r) / 2;
    if(qpos <= mid)
    {
        Update(l, mid, pos * 2, qpos, qval);
    }
    else
    {
        Update(mid + 1, r, pos * 2 + 1, qpos, qval);
    }
    seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
}

int Query(int l, int r, int pos, int ql, int qr)
{
    if(ql <= l && r <= qr)
    {
        return seg[pos];
    }
    if(ql > r || l > qr)
    {
        return INF;
    }
    int mid = (l + r) / 2;
    return min(Query(l, mid, pos * 2, ql, qr), Query(mid + 1, r, pos * 2 + 1, ql, qr));
}
 
int32_t sequence(int32_t n, vector<int32_t> a) 
{
    vector<int32_t> b = a;
    sort(b.begin(), b.end());
    int median1 = (n - 1) / 2, median2 = n / 2;
    if(b[median1] != 2)
    {
        return print_occ(b[median1], b);
    }
    if(b[median2] != 2)
    {
        return print_occ(b[median2], b);
    }
    int ans = print_occ(b[median2], b);
    for(int check = 1; check <= 3; check += 2)
    {
        vector<int> pref(n, 0);
        Build(0, 2 * n, 1);
        int cur_cnt = n;
        for(int i = 0; i < n; i++)
        {
            cur_cnt = (a[i] == check) ? cur_cnt + 1 : cur_cnt - 1;
            pref[i] = (i == 0) ? 0 : pref[i - 1];
            if(a[i] == check)
            {
                pref[i] += 1;
            }
            Update(0, 2 * n, 1, cur_cnt, i);
            int min_ans = Query(0, 2 * n, 1, 0, cur_cnt);
            if(min_ans == INF)
            {
                continue;
            }
            int this_ans = (min_ans == 0) ? pref[i] : pref[i] - pref[min_ans - 1];
            ans = max(ans, this_ans);
        }
    }
    return ans;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 76 ms 6100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 6116 KB Output is correct
2 Correct 93 ms 6100 KB Output is correct
3 Incorrect 89 ms 6112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -