QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#247436#7627. Phonyucup-team896#RE 0ms3652kbC++239.9kb2023-11-11 14:24:532023-11-11 14:24:53

Judging History

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

  • [2023-11-11 14:24:53]
  • 评测
  • 测评结果：RE
  • 用时：0ms
  • 内存：3652kb
查看
  • [2023-11-11 14:24:53]
  • 提交

answer

/*
 * @Author:             cmk666
 * @Created time:       2023-11-11 13:23:15
 * @Last Modified time: 2023-11-11 14:24:39
 */
#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->lc->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捏
// 伊娜可爱捏 伊娜贴贴捏
源文件, 语言: C++23

详细

Test #1:

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

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: 3652kb

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
Runtime Error

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:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-12 09:54:21 | 开源项目