QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#247451#7627. Phonyucup-team896#WA 0ms3608kbC++239.9kb2023-11-11 14:28:302023-11-11 14:28:31

Judging History

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

  • [2023-11-11 14:28:31]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3608kb
查看
  • [2023-11-11 14:28:30]
  • 提交

answer

/*
 * @Author:             cmk666
 * @Created time:       2023-11-11 13:23:15
 * @Last Modified time: 2023-11-11 14:28:17
 */
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include"debug.h"
#else
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
// ------------------------------
// #define IN_HAS_NEG
#define OUT_HAS_NEG
// #define CHK_EOF
// #define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#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
#ifdef LOCAL
	inline char gc() { return getchar(); }
	inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
	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);
#ifdef CHK_EOF
			if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
		}
		return *_read_ptr++;
	}
#else
	INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
	inline char gc() { return *_read_ptr++; }
#endif
	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
	{
		inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
	}	_auto_flush;
#endif
#ifdef CHK_EOF
	inline constexpr bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
	inline constexpr bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
	inline constexpr bool _isdigit(char c) { return c & 16; }
	inline constexpr bool _isgraph(char c) { return c > 32; }
#endif
	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;
#undef INLINE_V
	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();
	}
#ifdef IN_HAS_NEG
	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 >
#else
	template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
	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); }
#ifdef OUT_HAS_NEG
	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 >
#else
	template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
	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 println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
namespace FHQ
{
	mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
	struct node
	{
		node *lc, *rc; unsigned pri; ll v, mn, lz; int sz;
		node(ll x) : lc(nullptr), rc(nullptr), pri(rnd()), v(x), mn(x), lz(0), sz(1) {}
	};
	inline int sz(node *t) { return t ? t->sz : 0; }
	inline void pu(node *t)
	{
		t->sz = sz(t->lc) + sz(t->rc) + 1, t->mn = t->v;
		if ( t->lc ) t->mn = min(t->mn, t->lc->v);
		if ( t->rc ) t->mn = min(t->mn, t->rc->v);
	}
	inline void pd(node *t)
	{
		if ( !t->lz ) return;
		if ( t->lc ) t->lc->lz += t->lz;
		if ( t->rc ) t->rc->lz += t->lz;
		t->v -= t->lz, t->mn -= t->lz, t->lz = 0;
	}
	inline pair < node *, node * > split(node *t, int k)
	{
		if ( !t ) return make_pair(nullptr, nullptr);
		pd(t);
		if ( k <= sz(t->lc) )
		{
			auto tt = split(t->lc, k); t->lc = tt.second, pu(t);
			return make_pair(tt.first, t);
		}
		else
		{
			auto tt = split(t->rc, k - sz(t->lc) - 1); t->rc = tt.first, pu(t);
			return make_pair(t, tt.second);
		}
	}
	inline pair < node *, node * > split_(node *t, ll v)
	{
		if ( !t ) return make_pair(nullptr, nullptr);
		pd(t);
		if ( t->v > v )
		{
			auto tt = split_(t->lc, v); t->lc = tt.second, pu(t);
			return make_pair(tt.first, t);
		}
		else
		{
			auto tt = split_(t->rc, v); t->rc = tt.first, pu(t);
			return make_pair(t, tt.second);
		}
	}
	inline node *merge(node *l, node *r)
	{
		if ( !l ) return r;
		if ( !r ) return l;
		pd(l), pd(r);
		if ( l->pri < r->pri ) { l->rc = merge(l->rc, r), pu(l); return l; }
		else                   { r->lc = merge(l, r->lc), pu(r); return r; }
	}
} using FHQ::node, FHQ::pd, FHQ::split, FHQ::merge;
int n, m, p, sz, pos; char op; node *rt; ll a[500009], k, x, tag, mn, c0, c1;
inline void ins(ll x) { auto [l, r] = split_(rt, x); rt = merge(l, merge(new node(x), r)); }
inline void mdf(ll x)
{
	pd(rt), mn = rt->mn - tag, c0 = x / sz, c1 = ( mn - a[pos - 1] ) / k;
	if ( pos == 1 || c0 <= c1 )
	{
		tag += c0 * k;
		if ( x %= sz )
		{
			auto [l, r] = split(rt, sz - x);
			r->lz += k, rt = merge(r, l), pd(rt), mn = rt->mn - tag;
			while ( pos > 1 && a[pos - 1] >= mn ) ins(a[--pos] + tag), sz++;
		}
		return;
	}
	tag += ( c1 + 1 ) * k, mn -= ( c1 + 1 ) * k, x -= ( c1 + 1 ) * sz;
	while ( pos > 1 && a[pos - 1] >= mn ) ins(a[--pos] + tag), sz++;
	mdf(x);
}
int main()
{
	read(n, m, k);
	For(i, 1, n) read(a[i]);
	sort(a + 1, a + n + 1), rt = new node(a[n]), sz = 1, pos = n;
	For(_, 1, m)
	{
		read(op);
		if ( op == 'C' ) read(x), mdf(x);
		if ( op == 'A' )
		{
			read(p);
			if ( p > sz ) { println(a[n + 1 - p]); continue; }
			auto [l, _] = split(rt, sz - p); auto [m, r] = split(_, 1);
			println(m->v - tag), rt = merge(l, merge(m, r)); 
		}
	}
	return 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5 5
7 3 9
A 3
C 1
A 2
C 2
A 3

output:

3
4
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5 8 8
294 928 293 392 719
A 4
C 200
A 5
C 10
A 2
C 120
A 1
A 3

output:

294
200
191
0
-2

result:

ok 5 lines

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

100 100 233
5101 8001 6561 6329 6305 7745 4321 811 49 1121 3953 8054 8415 9876 6701 4097 6817 6081 495 5521 2389 2042 4721 8119 7441 7840 8001 5756 5561 129 1 5981 4801 7201 8465 7251 6945 5201 5626 3361 5741 3650 7901 2513 8637 3841 5621 9377 101 3661 5105 4241 5137 7501 5561 3581 4901 561 8721 811...

output:

6881
9161
4721
8200
2945
7647
7556
5291
5001
2042
4721
4721
6881
4097
7187
7218
7035
7018
811
6752
2561
6701
6114
6133
3581
5291
1485
5957
5393
2042
5285
5171
5205
4721
5084
4029
4097
4591
4809
4578
4705
2042
4535
4454
4603
4435
3581
4335
115
2042
4274
2042
4273
1485
4356
-17557

result:

wrong answer 7th lines differ - expected: '7531', found: '7556'
English 繁體中文 简体中文

Server Time: 2024-12-12 07:14:23 | OpenSource Project