分块题:loj上提交AC,devc++&luogu都显示CE
  • 板块学术版
  • 楼主pengyule
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/7/17 14:13
  • 上次更新2023/11/6 22:57:59
查看原帖
分块题:loj上提交AC,devc++&luogu都显示CE
300078
pengyule楼主2020/7/17 14:13

如题所述请问这是怎么回事

原评测结果

            In file included from /usr/include/c++/8/bits/stl_algobase.h:65,
                 from /usr/include/c++/8/bits/char_traits.h:39,
                 from /usr/include/c++/8/ios:40,
                 from /usr/include/c++/8/ostream:38,
                 from /usr/include/c++/8/iostream:39,
                 from /tmp/tmplbpdbka6/src:1:
/usr/include/c++/8/bits/stl_iterator_base_types.h: In instantiation of ‘struct std::iterator_traits<int>’:
/usr/include/c++/8/bits/stl_algo.h:4074:5:   required by substitution of ‘template<class _IIter, class _Tp> typename std::iterator_traits<_Iterator>::difference_type std::count(_IIter, _IIter, const _Tp&) [with _IIter = int; _Tp = int]’
/tmp/tmplbpdbka6/src:32:31:   required from here
/usr/include/c++/8/bits/stl_iterator_base_types.h:168:53: 错误:‘int’不是类、结构或联合类型
       typedef typename _Iterator::iterator_category iterator_category;
                                                     ^~~~~~~~~~~~~~~~~
/usr/include/c++/8/bits/stl_iterator_base_types.h:169:53: 错误:‘int’不是类、结构或联合类型
       typedef typename _Iterator::value_type        value_type;
                                                     ^~~~~~~~~~
/usr/include/c++/8/bits/stl_iterator_base_types.h:170:53: 错误:‘int’不是类、结构或联合类型
       typedef typename _Iterator::difference_type   difference_type;
                                                     ^~~~~~~~~~~~~~~
/usr/include/c++/8/bits/stl_iterator_base_types.h:171:53: 错误:‘int’不是类、结构或联合类型
       typedef typename _Iterator::pointer           pointer;
                                                     ^~~~~~~
/usr/include/c++/8/bits/stl_iterator_base_types.h:172:53: 错误:‘int’不是类、结构或联合类型
       typedef typename _Iterator::reference         reference;
                                                     ^~~~~~~~~

估计是有stl调用不符合规定

(最小众数)附代码↓感谢大家付出宝贵时间!

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#define ub upper_bound
#define lb lower_bound
const int N = 1e5 + 10, M = 5e3 + 5, Inf = 2147483627;
int a[N], dis[N], cnt[N];
int belong[N], f[M][M], lt[M], rt[M];
vector<int> C[N];
map<int, int> w;
int count(int x, int l, int r) { return ub(C[x].begin(), C[x].end(), r) - lb(C[x].begin(), C[x].end(), l); }
int query(int l, int r) {
    if (belong[l] == belong[r]) {
        int b = Inf, ans = 0;
        memset(cnt, 0, sizeof(cnt));
        for (int i = l; i <= r; i++) {
            cnt[a[i]]++;
            if (ans < cnt[a[i]])
                ans = cnt[a[i]], b = a[i];
            else if (ans == cnt[a[i]])
                b = min(b, a[i]);
        }
        return b;
    }
    int ans = 0, b = Inf, qty;
    for (int i = l; i <= rt[belong[l]]; i++) {
        qty = count(a[i], l, r);
        if (qty > ans)
            ans = qty, b = a[i];
        else if (qty == ans)
            b = min(b, a[i]);
    }
    for (int i = lt[belong[r]]; i <= r; i++) {
        qty = count(a[i], l, r);
        if (qty > ans)
            ans = qty, b = a[i];
        else if (qty == ans)
            b = min(b, a[i]);
    }
    if (belong[l] + 1 <= belong[r] - 1) {
        qty = count(f[belong[l] + 1][belong[r] - 1], l, r);
        if (ans < qty)
            ans = qty, b = f[belong[l] + 1][belong[r] - 1];
        else if (ans == qty)
            b = min(b, f[belong[l] + 1][belong[r] - 1]);
    }
    return b;
}
int read();
void print(int x);
void solution() {
    int n, val, l, r;
    n = read();
    val = 80;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        belong[i] = (i - 1) / val + 1;
        dis[++dis[0]] = a[i];
    }
    sort(dis + 1, dis + dis[0] + 1);
    for (int i = 1; i <= dis[0]; i++) w[dis[i]] = i;
    for (int i = 1; i <= n; i++) a[i] = w[a[i]];
    for (int i = 1; i <= n; i++) C[a[i]].push_back(i);
    for (int i = 1; i <= belong[n]; i++) lt[i] = (i - 1) * val + 1, rt[i] = i * val;
    rt[belong[n]] = n;
    for (int i = 1; i <= belong[n]; i++) {
        memset(cnt, 0, sizeof(cnt));
        int b = Inf, ans = -Inf;
        for (int j = i; j <= belong[n]; j++) {
            for (int k = lt[j]; k <= rt[j]; k++) {
                cnt[a[k]]++;
                if (cnt[a[k]] > ans)
                    ans = cnt[a[k]], b = a[k];
                else if (cnt[a[k]] == ans)
                    b = min(b, a[k]);
            }
            f[i][j] = b;
        }
    }
    for (int i = 1; i <= n; i++) {
        l = read();
        r = read();
        print(dis[query(l, r)]);
        puts("");
    }
}
int main() {
    ios::sync_with_stdio(false);
    solution();
    return 0;
}
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x * f;
}
void print(int x) {
    if (x / 10)
        print(x / 10);
    putchar(x % 10 + '0');
}
2020/7/17 14:13
加载中...