QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310913#7904. Rainbow SubarrayKiharaToumaRE 426ms23376kbC++148.1kb2024-01-21 19:40:492024-01-21 19:40:49

Judging History

你现在查看的是最新测评结果

  • [2024-06-09 00:00:26]
  • hack成功，自动添加数据
  • (/hack/652)
  • [2024-01-21 19:40:49]
  • 评测
  • 测评结果：RE
  • 用时：426ms
  • 内存：23376kb
查看
  • [2024-01-21 19:40:49]
  • 提交

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);
					del(a[r+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;
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 15884kb

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: 0
Accepted
time: 426ms
memory: 23376kb

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
3
2
6
5
7
2
4
1
4
1
1
3
2
2
7
8
7
7
1
7
6
2
4
3
1
6
7
7
3
4
3
9
3
8
6
6
3
1
6
3
1
2
4
6
4
6
4
1
4
7
1
6
3
5
6
6
1
7
5
3
1
6
4
5
3
2
2
6
2
3
10
1
4
3
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
8
4
8
3
2
8
4
5
6
2
6
2
4
1
5
4
5
3
2
4
1
2
1
4
5
8
3
7
3
3
3...

result:

ok 11102 lines

Test #3:

score: -100
Runtime Error

input:

1
500000 17244641009859
54748096 75475634 204928248 276927808 84875072 103158867 27937890 322595515 186026685 45468307 69240390 139887597 188586447 373764525 121365644 310156469 185188306 60350786 211308832 384695957 370562147 208427221 35937909 267590963 126478310 275357775 55361535 335993561 36696...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 02:40:32 | OpenSource Project