QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #310906 | #7904. Rainbow Subarray | KiharaTouma | WA | 457ms | 24596kb | C++14 | 8.1kb | 2024-01-21 19:37:58 | 2024-01-21 19:37:59 |
Judging History
answer
//qoj7904
#include <bits/stdc++.h>
using namespace std; typedef long long ll; namespace FastIO {
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc() { if (__builtin_expect(_read_ptr == _read_ptr_end, false)) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;} return *_read_ptr++; }
INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } }
INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; inline bool _isdigit(char c) { return (c & 16) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; }
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer; template <class T> INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed; template <class T> INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <> INLINE_V constexpr bool _is_integer<__int128> = true; template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true; template <> INLINE_V constexpr bool _is_signed<__int128> = true; template <> INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
inline void read(char &c) { do c = gc(); while (!_isgraph(c)); } inline void read_cstr(char *s) { char c = gc(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) s.push_back(c), c = gc(); }
template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void read(T &x) { char c = gc(); bool f = true; x = 0; while (!_isdigit(c)) { if (c == 45) f = false; c = gc(); }
if (f) while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); else while (_isdigit(c)) x = x * 10 - (c & 15), c = gc(); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void read(T &x) { char c = gc(); while (!_isdigit(c)) c = gc(); x = 0; while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); }
inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while (*s) pc(*s++); } inline void write(const string &s) { for (char c : s) pc(c); } template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; if (x >= 0) do buffer[digits++] = (x % 10) | 48, x /= 10; while (x);
else { pc(45); do buffer[digits++] = -(x % 10) | 48, x /= 10; while (x); } while (digits) pc(buffer[--digits]); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; do buffer[digits++] = (x % 10) | 48, x /= 10; while (x); while (digits) pc(buffer[--digits]); }
template <int N> struct _tuple_io_helper { template <class... T> static inline void _read(tuple<T...> &x) { _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x)); } };
template <> struct _tuple_io_helper<1> { template <class... T> static inline void _read(tuple<T...> &x) { read(get<0>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { write(get<0>(x)); } };
template <class... T> inline void read(tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_read(x); } template <class... T> inline void write(const tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_write(x); }
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); } template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first), pc(32), write(x.second); }
template <class T1, class... T2> inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template <class... T> inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template <class T1, class... T2> inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template <class... T> inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template <class T> inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template <class T1, class... T2> inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template <class... T> inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template <class... T> inline void println(const T &...x) { print(x...), pc(10); } template <class... T> inline void printk(const T &...x) { print(x...), pc(32); } template <class... T> inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; void solve();int main(){ solve(); return 0; }
const int N = 5e5 + 10;
int T, n, a[N];
ll k, bit[N], bb[N], b[N];
void add(int x, ll v){
while(x <= n){
bit[x] += v;
x += x & -x;
}
}
void addd(int x, ll v){
while(x <= n){
bb[x] += v;
x += x & -x;
}
}
ll ask(int x){
ll res = 0;
while(x){
res += bit[x];
x -= x & -x;
}
return res;
}
ll askk(int x){
ll res = 0;
while(x){
res += bb[x];
x -= x & -x;
}
return res;
}
int ch[N][2], val[N], pri[N], siz[N], tot;
int root, x, y, z;
void update(int x){
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
int newnode(int v){
siz[++tot] = 1;
val[tot] = v;
pri[tot] = rand();
return tot;
}
int merge(int x, int y){
if(!x || !y){
return x + y;
}
if(pri[x] < pri[y]){
ch[x][1] = merge(ch[x][1], y);
update(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
update(y);
return y;
}
}
void split(int p, int k, int &x, int &y){
if(!p){
x = y = 0;
return;
}
if(val[p] <= k){
x = p;
split(ch[p][1], k, ch[p][1], y);
} else {
y = p;
split(ch[p][0], k, x, ch[p][0]);
}
update(p);
}
int kth(int p, int k){
while(true){
if(k <= siz[ch[p][0]]){
p = ch[p][0];
} else if(k == siz[ch[p][0]] + 1){
return p;
} else {
k -= siz[ch[p][0]] + 1;
p = ch[p][1];
}
}
}
void ins(int k){
split(root, k, x, y);
root = merge(merge(x, newnode(k)), y);
}
void del(int k){
split(root, k, x, z);
split(x, k-1, x, y);
y = merge(ch[y][0], ch[y][1]);
root = merge(merge(x, y), z);
}
int getval(int k){
return val[kth(root, k)];
}
void solve(){
read(T);
while(T--){
// ins(-2e9);
// ins(2e9);
read(n, k);
for(int i = 1; i <= n; ++ i){
read(a[i]);
a[i] -= i;
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int m = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; ++ i){
a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
}
int ans = 1;
add(a[1], b[a[1]]);
addd(a[1], 1);
ins(a[1]);
for(int l = 1, r = 1; l <= n; ++ l){
r = max(r, l-1);
while(r < n){
add(a[r+1], b[a[r+1]]);
addd(a[r+1], 1);
ins(a[r+1]);
int rr = ((r+1) - l + 1) / 2 + 1;
int mid = getval(rr);
ll val = b[mid] * askk(mid-1) - ask(mid-1);
val += ask(m) - ask(mid) - b[mid] * (askk(m) - askk(mid));
if(abs(val) <= k){
ans = max(ans, (r+1) - l + 1);
++ r;
} else {
add(a[r+1], -b[a[r+1]]);
addd(a[r+1], -1);
break;
}
}
add(a[l], -b[a[l]]);
addd(a[l], -1);
del(a[l]);
}
println(ans);
for(int i = 1; i <= n; ++ i){
bit[i] = bb[i] = b[i] = 0;
}
for(int i = 1; i <= tot; ++ i){
ch[i][0] = ch[i][1] = siz[i] = val[i] = pri[i] = 0;
}
tot = root = 0;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15876kb
input:
5 7 5 7 2 5 5 4 11 7 6 0 100 3 4 5 99 100 5 6 1 1 1 1 1 5 50 100 200 300 400 500 1 100 3
output:
4 3 5 1 1
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 457ms
memory: 24596kb
input:
11102 2 167959139 336470888 134074578 5 642802746 273386884 79721198 396628655 3722503 471207868 6 202647942 268792718 46761498 443917727 16843338 125908043 191952768 2 717268783 150414369 193319712 6 519096230 356168102 262263554 174936674 407246545 274667941 279198849 9 527268921 421436316 3613460...
output:
1 4 1 2 6 5 7 2 4 1 4 1 1 3 2 2 7 8 7 7 1 7 5 2 4 3 1 6 7 7 3 4 3 9 3 8 6 6 2 1 5 2 1 2 4 5 4 6 4 1 4 7 1 6 3 5 6 6 1 7 5 3 1 6 3 5 3 2 2 6 2 3 10 1 4 4 2 4 5 1 7 5 5 5 8 5 3 6 3 5 5 8 5 4 5 2 1 5 2 3 3 4 8 1 3 1 2 2 8 3 1 6 8 1 8 4 5 6 6 7 4 8 3 2 8 4 5 6 2 6 2 4 1 5 4 5 3 2 4 1 2 1 3 3 8 3 7 3 3 2...
result:
wrong answer 3rd lines differ - expected: '3', found: '1'