글 읽기 - boj 2912 C/C++ Mo's 풀이

yohanroh 2년 전 0

Mo's Algorithm을 이용하여 풀었는데 왜 안되는지 잘 모르겠습니다.

//solution using mo's algorithm
#include <bits/stdc++.h>
using namespace std;
int n, m, v, c, s, e, sq;
int arr[300010], cnt[10010], ex[300010];
string ans[10010];
struct query {
    int s, e, c;
    bool operator < (query x) {
        return s / sq == x.s / sq ? e < x.e : s / sq < x.s / sq;
    }
} q[10010];
void add(int x) {
    ex[cnt[x]++]--, ex[cnt[x]]++;
    if (cnt[x] > v) v = cnt[x], c = x;
}
void sub(int x) {
    ex[cnt[x]--]--, ex[cnt[x]]++;
    if (!ex[v]) v = cnt[x], c = x;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> sq;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sq = (int)sqrt(n);
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> q[i].s >> q[i].e;
        q[i].s--, q[i].e--, q[i].c = i;
    }
    sort(q, q + m);
    add(arr[0]);
    for (int i = 0; i < m; i++) {
        while (s < q[i].s) sub(arr[s++]);
        while (s > q[i].s) add(arr[--s]);
        while (e < q[i].e) add(arr[++e]);
        while (e > q[i].e) sub(arr[e--]);
        ans[q[i].c] = v > (q[i].e - q[i].s + 1) / 2 ? "yes " + to_string(c) : "no";
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

ddddewang 1년 전 0

ex[v]가 2이상인 상황에서 c로 지정된 애가 sub되면 최대는 v지만 c가 최대를 가르키지는 않게 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

boj 2912 C/C++ Mo's 풀이

yohanroh 2년 전 0

ddddewang 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말