本地跑数据1是对的,为什么交上去就错了
评测记录
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int point;
char ch, stk[100];
const int N = 40010;
const int S = 210;
typedef double db;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;
#define il inline
#define ENDL putchar('\n')
#define GET(ch) ch = getchar()
#define PUT(ch) putchar(ch)
#define isd(ch) (ch >= 48 && ch <= 57)
#define mst(a, b) memset(a, b, sizeof(a))
#define rep(a, b, c) for (register int a = b; a <= c; ++ a)
#define drep(a, b, c) for (register int a = b; a >= c; -- a)
template <typename T>
il T Abs(T a) { return a < 0 ? -a : a; }
template <typename T>
il T Min(T a, T b) { return a < b ? a : b; }
template <typename T>
il T Max(T a, T b) { return a > b ? a : b; }
template <typename T>
il void Minn(T &a, T b) { a = a < b ? a : b; }
template <typename T>
il void Maxx(T &a, T b) { a = a > b ? a : b; }
template <typename T>
il void Swap(T &a, T &b) { T c = a; a = b; b = c; }
template <typename T>
il void read(T &x) {
T p = 1; x = 0; GET(ch);
while (!isd(ch)) {
if (ch == '-') p = -1;
GET(ch);
}
while (isd(ch))
x = (x << 1) + (x << 3) + (ch ^ 48), GET(ch);
x *= p;
}
template <typename T>
il void write(T x) {
point = 0;
if (x < 0) PUT('-'), x = -x;
do {
stk[++ point] = (x % 10 + 48);
} while (x /= 10);
while (point) PUT(stk[point --]);
}
int n, m, b[N], s[S][N], p[S][S];
int c[N], pos[N], l[S], r[S], bp[N];
struct flo {
int x, d;
bool operator < (const flo &c) const {
return d < c.d;
}
} a[N];
int maxx, pp, ss, ans;
il int query(int x, int y) {
if (pos[y] - pos[x] <= 1) {
pp = 0;
rep(i, x, y) {
++ c[b[i]];
if (c[b[i]] == c[pp]) Minn(pp, b[i]);
else if (c[b[i]] > c[pp]) pp = b[i];
}
rep(i, x, y) -- c[b[i]];
return pp;
}
ss = p[pos[x] + 1][pos[y] - 1];
maxx = s[pos[y] - 1][ss] - s[pos[x]][ss];
rep(i, x, r[pos[x]]) {
++ c[b[i]];
if (c[b[i]] + s[pos[y] - 1][b[i]] - s[pos[x]][b[i]] == maxx) ss = Min(ss, b[i]);
else if (c[b[i]] + s[pos[y] - 1][b[i]] - s[pos[x]][b[i]] > maxx) ss = b[i],
maxx = c[b[i]] + s[pos[y] - 1][b[i]] - s[pos[x]][b[i]];
}
rep(i, l[pos[y]], y) {
++ c[b[i]];
if (c[b[i]] + s[pos[y] - 1][b[i]] - s[pos[x]][b[i]] == maxx) ss = Min(ss, b[i]);
else if (c[b[i]] + s[pos[y] - 1][b[i]] - s[pos[x]][b[i]] > maxx) ss = b[i],
maxx = c[b[i]] + s[pos[y] - 1][b[i]] - s[pos[x]][b[i]];
}
rep(i, x, r[pos[x]]) -- c[b[i]];
rep(i, l[pos[y]], y) -- c[b[i]];
return ss;
}
int main() {
read(n), read(m);
rep(i, 1, n) read(a[i].d), a[i].x = i;
sort(a + 1, a + n + 1);
int now = 0, x, ql, qr, t = sqrt(n);
rep(i, 1, n) {
if (a[i - 1].d ^ a[i].d) ++ now;
b[a[i].x] = now; bp[now] = a[i].d;
}
rep(i, 1, t) {
l[i] = (i - 1) * t + 1; r[i] = i * t;
rep(j, 1, now) s[i][j] = s[i - 1][j];
rep(j, l[i], r[i])
++ s[i][b[j]], pos[j] = i;
}
if (r[t] < n) {
l[++ t] = r[t - 1] + 1, r[t] = n;
rep(i, 1, now) s[t][i] = s[t - 1][i];
rep(i, l[t], r[t])
++ s[t][b[i]], pos[i] = t;
}
rep(i, 1, t) {
mst(c, 0); pp = 0;
rep(j, i, t) {
rep(k, l[j], r[j]) {
++ c[b[k]];
if (c[pp] < c[b[k]]) pp = b[k];
if (c[pp] == c[b[k]]) Minn(pp, b[k]);
}
p[i][j] = pp;
}
} mst(c, 0);
rep(i, 1, m) {
read(x), ql = (x + ans - 1) % n + 1;
read(x), qr = (x + ans - 1) % n + 1;
if (ql > qr) Swap(ql, qr);
ans = bp[query(ql, qr)];
write(ans); ENDL;
}
return 0;
}