QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744110#2886. 区间众数TheZoneCompile Error//C++2014.0kb2024-11-13 20:54:032024-11-13 20:54:04

Judging History

This is the latest submission verdict.

  • [2024-11-13 20:54:04]
  • Judged
Show
  • [2024-11-13 20:54:03]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 5e5 + 5;
const int MAXQ = 1e6 + 5;
const int B = 2e2;
const int inf = 0x3f3f3f3f;

inline int read(void) {
    int res = 0;
    char c = getchar();

    while (c < '0' && c >= '9')
        c = getchar();

    while (c >= '0' && c <= '9')
        res = res * 10 + c - '0', c = getchar();

    return res;
}

struct BIT {
    int n;
    vector<ll> tree;
#define lowbit(x) ((x)&-(x))
    BIT(int _n = 0): n(_n), tree(n + 1, 0) {}
    void update(int x, ll k) {
        while (x <= n)
            tree[x] += k,
                       x += lowbit(x);
    }
    ll query(int x) {
        ll res = 0;

        while (x)
            res += tree[x],
                   x ^= lowbit(x);

        return res;
    }
};

struct Counter_2D {
    vector< pair<pii, int>> pt, qs;
    void insert(int x, int y, int k) {
        pt.emplace_back(make_pair(x, y), k);
    }
    int addquery(int x, int y) {
        qs.emplace_back(make_pair(x, y), qs.size());
        return (int)qs.size() - 1;
    }

    vector<ll> res;
    void build(void) {
        vector<int> dsc(pt.size());

        for (int i = 0; i < (int)pt.size(); ++i)
            dsc[i] = pt[i].first.second;

        sort(dsc.begin(), dsc.end());
        dsc.erase(unique(dsc.begin(), dsc.end()), dsc.end());
        auto get = [&](int x) {
            return upper_bound(dsc.begin(), dsc.end(), x) - dsc.begin();
        };

        sort(pt.begin(), pt.end());
        sort(qs.begin(), qs.end());

        res.resize(qs.size());
        BIT tree(dsc.size());

        for (int i = 0, j = 0; i < (int)qs.size(); ++i) {
            while (j < (int)pt.size() && pt[j].first.first <= qs[i].first.first)
                tree.update(get(pt[j].first.second), pt[j].second),
                            ++j;

            res[qs[i].second] = tree.query(get(qs[i].first.second));
        }
    }
};

/*
ans = sum min(min(A - l', B - r'), len')
    = sum min(A - l, B - r) * k

solve l <= A, r <= B, A - l <= B - r
->    l <= A, r - l <= B - A

solve l <= A, r <= B, A - l > B - r
->    r <= B, l - r < A - B

ans = sum (A - l) * k
    = sum (A * k - l * k)
    = A * sum (k) + sum (-l * k)
*/
struct Half_Solver {
    Counter_2D sumK, sumB;
    vector<int> qs;
    void _insert(int l, int r, int k) {
        sumK.insert(r - l, l, k);
        sumB.insert(r - l, l, -l * k);
    }
    void insert(int l, int r, int len) {
        _insert(l, r, 1);
        _insert(l + len, r + len, -1);
    }
    int addquery(int x, int y) {
        sumK.addquery(x, y);
        sumB.addquery(x, y);
        qs.push_back(y);
        return (int)qs.size() - 1;
    }

    vector<ll> res;
    void build(void) {
        sumK.build();
        sumB.build();
        res.resize(qs.size());

        for (int i = 0; i < (int)qs.size(); ++i)
            res[i] = (ll)sumK.res[i] * qs[i] + sumB.res[i];
    }
};

int n, Q;
int a[MAXN];
vector<int> apos[MAXN], keys[MAXN];
int rnk[MAXN];

int main(void) {
    n = read();
    Q = read();

    for (int i = 1; i <= n; ++i)
        a[i] = read();

    for (int i = 1; i <= n; ++i) {
        rnk[i] = apos[a[i]].size();
        apos[a[i]].push_back(i);
    }

    for (int i = 1; i <= n; ++i) {
        for (int x : apos[i])
            keys[i].push_back(abs(x - i));

        sort(keys[i].begin(), keys[i].end());
    }

    static vector<int> seg[MAXN];

    for (int i = 1; i <= n; ++i) {
        seg[i].resize(apos[i].size(), inf);

        for (int k = 0; k < (int)keys[i].size(); ++k) {
            if (k + 1 < (int)keys[i].size())
                seg[i][k] = min(seg[i][k], keys[i][k + 1] - 1);

            seg[i][k] = min(seg[i][k], i - 1);
            seg[i][k] = min(seg[i][k], n - i);
        }
    }

    vector<int> alive(n);
    iota(alive.begin(), alive.end(), 1);
    sort(alive.begin(), alive.end(), [&](int x, int y) {
        return apos[x].size() > apos[y].size();
    });

    for (int k = 0; k < B && alive.size(); ++k) {
        while (alive.size() && (int)apos[alive.back()].size() <= k)
            alive.pop_back();

        static int mxlef[MAXN];
        memset(mxlef, 0xc0, (n + 1) << 2);

        for (int i = 1; i <= n; ++i) {
            if (rnk[i] >= k + 1)
                mxlef[i] = apos[a[i]][rnk[i] - (k + 1)];

            mxlef[i] = max(mxlef[i], mxlef[i - 1]);
        }

        for (int i : alive) {
            auto chk = [&](int t) {
                return mxlef[i + t] < i - t;
            };

            int l = keys[i][k], r = min(i - 1, n - i);

            if (k + 1 < (int)apos[i].size())
                r = min(r, keys[i][k + 1] - 1);

            if (l > r || !chk(l)) {
                seg[i][k] = -inf;
                continue;
            }

            while (l < r) {
                int mid = (l + r + 1) >> 1;

                if (chk(mid))
                    l = mid;
                else
                    r = mid - 1;
            }

            seg[i][k] = l;
        }
    }

    sort(alive.begin(), alive.end());

    for (int j : alive) {
        const vector<int> &pos = apos[j];
        const int siz = (int)apos[j].size();
        int currnk = -1;

        for (int i : alive)
            if (i != j) {
                while (currnk + 1 < siz && pos[currnk + 1] < i)
                    ++currnk;

                int jl = currnk + 1, jr = currnk;
                auto onestep = [&](void) {
                    if (jl - 1 < 0 && jr + 1 >= siz)
                        return false;

                    if (jl - 1 < 0)
                        ++jr;
                    else if (jr + 1 >= siz)
                        --jl;
                    else {
                        if (i - pos[jl - 1] <= pos[jr + 1] - i)
                            --jl;
                        else
                            ++jr;
                    }

                    return true;
                };

                bool ok = 1;

                for (int k = -1; k < B && ok; ++k)
                    ok &= onestep();

                if (!ok)
                    continue;

                for (int k = B; k < (int)apos[i].size(); ++k) {
                    if (!onestep())
                        break;

                    int far = max(i - pos[jl], pos[jr] - i);
                    seg[i][k] = min(seg[i][k], far - 1);
                }
            }
    }

    Half_Solver slv1, slv2;

    for (int i = 1; i <= n; ++i)
        for (int k = 0; k < (int)apos[i].size(); ++k) {
            if (seg[i][k] < keys[i][k])
                continue;

            int l = i - keys[i][k], r = i + keys[i][k], len = seg[i][k] - keys[i][k] + 1;

            l = n - l + 1;
            slv1.insert(l, r, len);
            slv2.insert(r, l, len);
        }

    for (int i = 1; i <= Q; ++i) {
        int l = read(), r = read();

        int qA = (n - l + 1) + 1, qB = r + 1;
        slv1.addquery(qB - qA, qA);
        slv2.addquery(qA - qB - 1, qB);
    }

    slv1.build();
    slv2.build();

    for (int i = 1; i <= Q; ++i)
        printf("%lld\n", slv1.res[i - 1] + slv2.res[i - 1]);

    return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 5e5 + 5;
const int MAXQ = 1e6 + 5;
const int B = 2e2;
const int inf = 0x3f3f3f3f;

inline int read(void) {
    int res = 0;
    char c = getchar();

    while (c < '0' && c >= '9')
        c = getchar();

    while (c >= '0' && c <= '9')
        res = res * 10 + c - '0', c = getchar();

    return res;
}

struct BIT {
    int n;
    vector<ll> tree;
#define lowbit(x) ((x)&-(x))
    BIT(int _n = 0): n(_n), tree(n + 1, 0) {}
    void update(int x, ll k) {
        while (x <= n)
            tree[x] += k,
                       x += lowbit(x);
    }
    ll query(int x) {
        ll res = 0;

        while (x)
            res += tree[x],
                   x ^= lowbit(x);

        return res;
    }
};

struct Counter_2D {
    vector< pair<pii, int>> pt, qs;
    void insert(int x, int y, int k) {
        pt.emplace_back(make_pair(x, y), k);
    }
    int addquery(int x, int y) {
        qs.emplace_back(make_pair(x, y), qs.size());
        return (int)qs.size() - 1;
    }

    vector<ll> res;
    void build(void) {
        vector<int> dsc(pt.size());

        for (int i = 0; i < (int)pt.size(); ++i)
            dsc[i] = pt[i].first.second;

        sort(dsc.begin(), dsc.end());
        dsc.erase(unique(dsc.begin(), dsc.end()), dsc.end());
        auto get = [&](int x) {
            return upper_bound(dsc.begin(), dsc.end(), x) - dsc.begin();
        };

        sort(pt.begin(), pt.end());
        sort(qs.begin(), qs.end());

        res.resize(qs.size());
        BIT tree(dsc.size());

        for (int i = 0, j = 0; i < (int)qs.size(); ++i) {
            while (j < (int)pt.size() && pt[j].first.first <= qs[i].first.first)
                tree.update(get(pt[j].first.second), pt[j].second),
                            ++j;

            res[qs[i].second] = tree.query(get(qs[i].first.second));
        }
    }
};

/*
ans = sum min(min(A - l', B - r'), len')
    = sum min(A - l, B - r) * k

solve l <= A, r <= B, A - l <= B - r
->    l <= A, r - l <= B - A

solve l <= A, r <= B, A - l > B - r
->    r <= B, l - r < A - B

ans = sum (A - l) * k
    = sum (A * k - l * k)
    = A * sum (k) + sum (-l * k)
*/
struct Half_Solver {
    Counter_2D sumK, sumB;
    vector<int> qs;
    void _insert(int l, int r, int k) {
        sumK.insert(r - l, l, k);
        sumB.insert(r - l, l, -l * k);
    }
    void insert(int l, int r, int len) {
        _insert(l, r, 1);
        _insert(l + len, r + len, -1);
    }
    int addquery(int x, int y) {
        sumK.addquery(x, y);
        sumB.addquery(x, y);
        qs.push_back(y);
        return (int)qs.size() - 1;
    }

    vector<ll> res;
    void build(void) {
        sumK.build();
        sumB.build();
        res.resize(qs.size());

        for (int i = 0; i < (int)qs.size(); ++i)
            res[i] = (ll)sumK.res[i] * qs[i] + sumB.res[i];
    }
};

int n, Q;
int a[MAXN];
vector<int> apos[MAXN], keys[MAXN];
int rnk[MAXN];

int main(void) {
    n = read();
    Q = read();

    for (int i = 1; i <= n; ++i)
        a[i] = read();

    for (int i = 1; i <= n; ++i) {
        rnk[i] = apos[a[i]].size();
        apos[a[i]].push_back(i);
    }

    for (int i = 1; i <= n; ++i) {
        for (int x : apos[i])
            keys[i].push_back(abs(x - i));

        sort(keys[i].begin(), keys[i].end());
    }

    static vector<int> seg[MAXN];

    for (int i = 1; i <= n; ++i) {
        seg[i].resize(apos[i].size(), inf);

        for (int k = 0; k < (int)keys[i].size(); ++k) {
            if (k + 1 < (int)keys[i].size())
                seg[i][k] = min(seg[i][k], keys[i][k + 1] - 1);

            seg[i][k] = min(seg[i][k], i - 1);
            seg[i][k] = min(seg[i][k], n - i);
        }
    }

    vector<int> alive(n);
    iota(alive.begin(), alive.end(), 1);
    sort(alive.begin(), alive.end(), [&](int x, int y) {
        return apos[x].size() > apos[y].size();
    });

    for (int k = 0; k < B && alive.size(); ++k) {
        while (alive.size() && (int)apos[alive.back()].size() <= k)
            alive.pop_back();

        static int mxlef[MAXN];
        memset(mxlef, 0xc0, (n + 1) << 2);

        for (int i = 1; i <= n; ++i) {
            if (rnk[i] >= k + 1)
                mxlef[i] = apos[a[i]][rnk[i] - (k + 1)];

            mxlef[i] = max(mxlef[i], mxlef[i - 1]);
        }

        for (int i : alive) {
            auto chk = [&](int t) {
                return mxlef[i + t] < i - t;
            };

            int l = keys[i][k], r = min(i - 1, n - i);

            if (k + 1 < (int)apos[i].size())
                r = min(r, keys[i][k + 1] - 1);

            if (l > r || !chk(l)) {
                seg[i][k] = -inf;
                continue;
            }

            while (l < r) {
                int mid = (l + r + 1) >> 1;

                if (chk(mid))
                    l = mid;
                else
                    r = mid - 1;
            }

            seg[i][k] = l;
        }
    }

    sort(alive.begin(), alive.end());

    for (int j : alive) {
        const vector<int> &pos = apos[j];
        const int siz = (int)apos[j].size();
        int currnk = -1;

        for (int i : alive)
            if (i != j) {
                while (currnk + 1 < siz && pos[currnk + 1] < i)
                    ++currnk;

                int jl = currnk + 1, jr = currnk;
                auto onestep = [&](void) {
                    if (jl - 1 < 0 && jr + 1 >= siz)
                        return false;

                    if (jl - 1 < 0)
                        ++jr;
                    else if (jr + 1 >= siz)
                        --jl;
                    else {
                        if (i - pos[jl - 1] <= pos[jr + 1] - i)
                            --jl;
                        else
                            ++jr;
                    }

                    return true;
                };

                bool ok = 1;

                for (int k = -1; k < B && ok; ++k)
                    ok &= onestep();

                if (!ok)
                    continue;

                for (int k = B; k < (int)apos[i].size(); ++k) {
                    if (!onestep())
                        break;

                    int far = max(i - pos[jl], pos[jr] - i);
                    seg[i][k] = min(seg[i][k], far - 1);
                }
            }
    }

    Half_Solver slv1, slv2;

    for (int i = 1; i <= n; ++i)
        for (int k = 0; k < (int)apos[i].size(); ++k) {
            if (seg[i][k] < keys[i][k])
    for (int i = 1; i <= Q; ++i)
        printf("%lld\n", slv1.res[i - 1] + slv2.res[i - 1]);

    return 0;
}*/
源文件, 语言: C++20

詳細信息 

answer.code:387:8: error: redefinition of ‘struct Half_Solver’
  387 | struct Half_Solver {
      |        ^~~~~~~~~~~
answer.code:97:8: note: previous definition of ‘struct Half_Solver’
   97 | struct Half_Solver {
      |        ^~~~~~~~~~~
answer.code:416:5: error: redefinition of ‘int n’
  416 | int n, Q;
      |     ^
answer.code:126:5: note: ‘int n’ previously declared here
  126 | int n, Q;
      |     ^
answer.code:416:8: error: redefinition of ‘int Q’
  416 | int n, Q;
      |        ^
answer.code:126:8: note: ‘int Q’ previously declared here
  126 | int n, Q;
      |        ^
answer.code:417:5: error: redefinition of ‘int a [500005]’
  417 | int a[MAXN];
      |     ^
answer.code:127:5: note: ‘int a [500005]’ previously declared here
  127 | int a[MAXN];
      |     ^
answer.code:418:13: error: redefinition of ‘std::vector<int> apos [500005]’
  418 | vector<int> apos[MAXN], keys[MAXN];
      |             ^~~~
answer.code:128:13: note: ‘std::vector<int> apos [500005]’ previously defined here
  128 | vector<int> apos[MAXN], keys[MAXN];
      |             ^~~~
answer.code:418:25: error: redefinition of ‘std::vector<int> keys [500005]’
  418 | vector<int> apos[MAXN], keys[MAXN];
      |                         ^~~~
answer.code:128:25: note: ‘std::vector<int> keys [500005]’ previously defined here
  128 | vector<int> apos[MAXN], keys[MAXN];
      |                         ^~~~
answer.code:419:5: error: redefinition of ‘int rnk [500005]’
  419 | int rnk[MAXN];
      |     ^~~
answer.code:129:5: note: ‘int rnk [500005]’ previously declared here
  129 | int rnk[MAXN];
      |     ^~~
answer.code:421:5: error: redefinition of ‘int main()’
  421 | int main(void) {
      |     ^~~~
answer.code:131:5: note: ‘int main()’ previously defined here
  131 | int main(void) {
      |     ^~~~
answer.code: In function ‘int main()’:
answer.code:560:3: error: expected primary-expression before ‘/’ token
  560 | }*/
      |   ^
answer.code:560:4: error: expected primary-expression at end of input
  560 | }*/
      |    ^
answer.code:560:4: error: expected ‘}’ at end of input
answer.code:421:16: note: to match this ‘{’
  421 | int main(void) {
      |                ^
answer.code: At global scope:
answer.code:225:32: error: mangling of ‘main()::<lambda()>’ as ‘_ZZ4mainENKUlvE_clEv’ conflicts with a previous mangle
  225 |                 auto onestep = [&](void) {
      |                                ^
answer.code:515:32: note: previous mangling ‘main()::<lambda()>’
  515 |                 auto onestep = [&](void) {
      |                                ^
answer.code:225:32: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
  225 |                 auto onestep = [&](void) {
      |                                ^
answer.code:185:24: error: mangling of ‘main()::<lambda(int)>’ as ‘_ZZ4mainENKUliE_clEi’ conflicts with a previous mangle
  185 |             auto chk = [&](int t) {
      |                        ^
answer.code:475:24: note: previous mangling ‘main()::<lambda(int)>’
  475 |             auto chk = [&](int t) {
      |                        ^
answer.code:185:24: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
  185 |             auto chk = [&](int t) {
      |                        ^
English 繁體中文 简体中文

伺服器時間: 2025-03-06 13:56:46 | 開源專案