#525497 (C++14) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	Tqk
提出日時	2020-08-07 04:09:23
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	216 ms / 3,000 ms
コード長	12,398 bytes
コンパイル時間	3,288 ms
コンパイル使用メモリ	192,864 KB
実行使用メモリ	13,020 KB
最終ジャッジ日時	2024-09-22 10:13:04
合計ジャッジ時間	7,690 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 12,808 KB
testcase_01	AC	5 ms 12,816 KB
testcase_02	AC	4 ms 12,912 KB
testcase_03	AC	26 ms 12,720 KB
testcase_04	AC	56 ms 12,980 KB
testcase_05	AC	56 ms 12,848 KB
testcase_06	AC	59 ms 12,872 KB
testcase_07	AC	6 ms 12,856 KB
testcase_08	AC	5 ms 12,768 KB
testcase_09	AC	5 ms 12,688 KB
testcase_10	AC	5 ms 12,684 KB
testcase_11	AC	6 ms 12,696 KB
testcase_12	AC	93 ms 12,860 KB
testcase_13	AC	95 ms 12,708 KB
testcase_14	AC	92 ms 12,892 KB
testcase_15	AC	100 ms 12,768 KB
testcase_16	AC	98 ms 12,800 KB
testcase_17	AC	114 ms 12,828 KB
testcase_18	AC	123 ms 12,824 KB
testcase_19	AC	138 ms 12,816 KB
testcase_20	AC	143 ms 12,880 KB
testcase_21	AC	173 ms 12,840 KB
testcase_22	AC	177 ms 12,692 KB
testcase_23	AC	185 ms 12,908 KB
testcase_24	AC	203 ms 12,828 KB
testcase_25	AC	212 ms 12,888 KB
testcase_26	AC	216 ms 12,816 KB
testcase_27	AC	6 ms 13,020 KB
testcase_28	AC	7 ms 12,828 KB
testcase_29	AC	5 ms 12,852 KB
testcase_30	AC	88 ms 12,852 KB
testcase_31	AC	91 ms 12,844 KB
testcase_32	AC	6 ms 12,812 KB
testcase_33	AC	5 ms 12,872 KB
testcase_34	AC	6 ms 12,872 KB
testcase_35	AC	5 ms 12,880 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp:1:13: warning: extra tokens at end of #ifdef directive
    1 | #ifdef BODY ================================================================================================================================
      |             ^~
main.cpp:26:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
   26 | #endif BODY ================================================================================================================================
      |        ^~~~
main.cpp:234:9: warning: #pragma once in main file
  234 | #pragma once
      |         ^~~~
main.cpp:51:13: warning: integer suffix 'z' shadowed by implementation
   51 | inline lint operator""z(const unsigned long long n){ return lint(n); }
      |             ^~~~~~~~

ソースコード

raw source code

#ifdef BODY ================================================================================================================================

+library{ name:splay_tree_set, url:https://tqkoh.github.io/library/library/lib/data-structure/splay-tree-set.hpp, version:2020-08-07 }

int solve(){
	lin(q,k);
	Set s;
	while(q--){
		lint t,v; in(t);
		if(t==1){
			in(v);
			s.insert({v, q});
		}
		else{
			if(s.size()>=k){
				auto p = s.nth(k-1);
				out(p->val.first);
				s.erase(p->val);
			}
			else out(-1);
		}
	}
	return 0;
}

#endif BODY ================================================================================================================================

//sub-BOF

// desktop
// author: Tqk

//#define _AOJ_
//#define _C_INPUT_

#pragma region template

#pragma region basic
#define IN_FILE "./in.txt"
//#pragma GCC optimize ("O3")
#pragma warning(disable: 4455 4244 4067 4068 4996)
#pragma GCC target ("avx")
#pragma GCC diagnostic ignored "-Wliteral-suffix"
#define NOMINMAX
#include "bits/stdc++.h"
using namespace std;
typedef int64_t lint;
typedef long double ld;
typedef string cs;
#define linf 1152921504606846976
inline lint operator""z(const unsigned long long n){ return lint(n); }
#pragma endregion

#pragma region rep
#define _vcppunko4(tuple) _getname4 tuple
#define _getname4(_1,_2,_3,_4,name,...) name
#define _getname3(_1,_2,_3,name,...) name
#define _trep2(tuple) _rep2 tuple
#define _trep3(tuple) _rep3 tuple
#define _trep4(tuple) _rep4 tuple
#define _rep1(n) for(lint i=0;i<n;++i)
#define _rep2(i,n) for(lint i=0;i<n;++i)
#define _rep3(i,a,b) for(lint i=a;i<b;++i)
#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)
#define _trrep2(tuple) _rrep2 tuple
#define _trrep3(tuple) _rrep3 tuple
#define _trrep4(tuple) _rrep4 tuple
#define _rrep1(n) for(lint i=n-1;i>=0;--i)
#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)
#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)
#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))
#define per(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__))
#define each(c) for(auto &e:c)
#pragma endregion

#pragma region io
template<class T>
istream& operator>>(istream& is,vector<T>& vec);
template<class T,size_t size>
istream& operator>>(istream& is,array<T,size>& vec);
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p);
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec);
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p);
template<class T>
istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }
template<class T>
ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }
template<class T>
ostream& operator<<(ostream& os,set<T>& s){ each(s)os<<e<<" ";return os; }

#ifdef __ENV_TQK__
/*
ifstream infile(IN_FILE);
template<class T>
ifstream& operator>>(ifstream& is,vector<T>& vec);
template<class T,size_t size>
ifstream& operator>>(ifstream& is,array<T,size>& vec);
template<class T,class L>
ifstream& operator>>(ifstream& is,pair<T,L>& p);
template<class T>
ifstream& operator>>(ifstream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
ifstream& operator>>(ifstream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
inline void fin(){}
template <class Head,class... Tail>
inline void fin(Head&& head,Tail&&... tail){ infile>>head;fin(move(tail)...); }
*/
#include<Windows.h>
HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
inline void in(){ SetConsoleTextAttribute(hConsole,10); }
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){
	SetConsoleTextAttribute(hConsole,15);
	cin>>head;in(move(tail)...);
}
#else
inline void in(){}
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }
#endif

inline bool out(){ return(cout<<'\n',0); }
template <class T>
inline bool out(T t){ return(cout<<t<<'\n',0); }
template <class Head,class... Tail>
inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }
template <class T>
inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); }
#define alc alloc
#ifdef __ENV_TQK__
inline bool deb(){ SetConsoleTextAttribute(hConsole,10); return(cout<<'\n',0); }
template <class T>
inline bool deb(T t){ return(SetConsoleTextAttribute(hConsole,12),cout<<t<<'\n',SetConsoleTextAttribute(hConsole,10),0); }
template <class Head,class... Tail>
inline bool deb(Head head,Tail... tail){
	SetConsoleTextAttribute(hConsole,12);
	cout<<head<<' ';deb(move(tail)...);return 0;
}
#define dsp(ex) sp(ex)
#define dno(ex) no(ex)
#define look(v) SetConsoleTextAttribute(hConsole,12),cout<<#v<<": ",deb(v);
#else
#define deb(...) 0
#define dsp(ex) 0
#define dno(ex) 0
#define look(v) 0
#endif

#pragma endregion

#pragma region TA
#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)
#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)
#define vin(type,name,size) vector<type> name(size);in(name)
#define all(v) v.begin(),v.end()
#define pb push_back
#define fi e.first
#define se e.second
#define YES(c) cout<<((c)?"YES\n":"NO\n"),0
#define Yes(c) cout<<((c)?"Yes\n":"No\n"),0
#define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0
#define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0
#define o(p) cout<<p<<endl,0
#define sp(p) cout<<p<<" ",0
#define no(p) cout<<p,0
#define psort(l,r) if(l>r)swap(l,r);
inline constexpr lint gcd(lint a,lint b){ while(b){ lint c=b;b=a%b;a=c; }return a; }
inline constexpr lint lcm(lint a,lint b){ return a/gcd(a,b)*b; }
template<typename T>
inline constexpr bool chmin(T &mn,const T &cnt){ if(mn>cnt){ mn=cnt;return 1; } else return 0; }
template<typename T>
inline constexpr bool chmax(T &mx,const T &cnt){ if(mx<cnt){ mx=cnt;return 1; } else return 0; }
#define fn(ty1,ty2,ex) [](ty1 l,ty2 r){ return(ex); }
#define lfn(ex) [](lint l,lint r){ return(ex); }

#pragma endregion

#pragma region P
class P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; };
istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; }
constexpr bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); }
constexpr bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); }
constexpr bool operator<=(const P& l,const P& r){ return!(l.f-r.f?l.f>r.f:l.s>r.s); }
constexpr bool operator>=(const P& l,const P& r){ return!(l.f-r.f?l.f<r.f:l.s<r.s); }
P operator+(const P& l,const P& r){return P(l.f+r.f,l.s+r.s);}
P operator-(const P& l,const P& r){return P(l.f-r.f,l.s-r.s);}
P operator-(const P& r){return P(-r.f,-r.s); }
P operator*(const lint& l,const P& r){return P(l*r.f,l*r.s); }
P operator/(const P& l,const lint& r){return P(l.f/r,l.s/r); }
#pragma endregion

#pragma region start
struct Start{
	Start(){
#ifndef _C_INPUT_
		cin.tie(0),cout.tie(0);
		ios::sync_with_stdio(0);
#endif
		cout<<fixed<<setprecision(16);
	}
} __start;
#pragma endregion

#pragma endregion

#pragma region const
#define MAXN 101010
#define mod 1000000007
const ld pi=acos(-1);
const ld tau=(1.+sqrt(5))/2.;
P d4[4]={P(1,0),P(0,1),P(-1,0),P(0,-1)};
P d8[8]={P(1,0),P(1,1),P(0,1),P(-1,1),P(-1,0),P(-1,-1),P(0,-1),P(1,-1)};
const string AUTO_YES = "Yay!";
const string AUTO_NO = ":(";
int cho(bool c,cs yes=AUTO_YES,cs no=AUTO_NO){
	return out((c?yes:no));
}
#pragma endregion

#pragma region solve

#pragma region lib_splay_tree_set

#pragma once
const int MAX_SIZE = 200020;

using T = pair<lint,int>;
class Set{
public:
	struct Node{
		Node* l,* r,* p;
		int size;
		T val;
		Node():l(nullptr),r(nullptr),p(nullptr),size(1),val(T()){}
		void rotate(){
			Node* c;
			if(p->l==this){
				c = r;
				r = p;
				p->l = c;
			}
			else{
				c = l;
				l = p;
				p->r = c;
			}
			if(p->p && p->p->l == p)p->p->l = this;
			if(p->p && p->p->r == p)p->p->r = this;

			Node* prv_p = p;
			p = p->p;
			prv_p->p = this;
			if(c)c->p = prv_p;

			prv_p->update();
			update();
		}
		int pdirection(){
			if(!p)return 0;
			return p->l == this ? 1 : -1;
		}
		Node* splay(){
			while(pdirection()){
				if(!p->pdirection()){
					rotate();
				}
				else if(p->pdirection() == pdirection()){
					p->rotate();
					rotate();
				}
				else{
					rotate();
					rotate();
				}
			}
			return this;
		}

		void update(){
			size = 1;
			if(l)size += l->size;
			if(r)size += r->size;
		}
	};

private:
	static Node node[MAX_SIZE];
	static int _size;
	Node* _root;

public:
	Set(): _root(nullptr){};

	Node* root(){ return _root; }
	int size(){
		if(!root()) return 0;
		return root()->size;
	}

	Node* nth(int n){
		if(n >= size())return nullptr;
		Node* cur = root();
		while(cur){
			int lsize = cur->l ? cur->l->size : 0;
			if(n < lsize){
				cur = cur->l;
			}
			else if(n == lsize){
				return _root = cur->splay();
			}
			else{
				cur = cur->r;
				n -= lsize + 1;
			}
		}

		return nullptr;
	}
	bool find(T x){
		Node* cur = root(),* prv = nullptr;
		while(cur){
			prv = cur;
			if(x < cur->val){
				cur = cur->l;
			}
			else if(x == cur->val){
				_root = cur->splay();
				return 1;
			}
			else{
				cur = cur->r;
			}
		}
		prv ? _root = prv->splay() : nullptr;
		return 0;
	}
	void merge(Node* r_root){
		if(!r_root)return;
		nth(size() - 1);
		root()->r = r_root;
		r_root->p = root();
		root()->update();
	}
	void merge(Set& s){
		merge(s.root());
	}
	void insert(T x){
		if(!find(x)){
			node[_size].val = x;
			if(!root()){
				_root = node + _size++;
				return;
			}
			if(x < root()->val){
				node[_size].r = root();
				root()->p = node + _size;
				if(root()->l){
					node[_size].l = root()->l;
					root()->l->p = node + _size;
					root()->l = nullptr;
				}
			}
			else{
				node[_size].l = root();
				root()->p = node + _size;
				if(root()->r){
					node[_size].r = root()->r;
					root()->r->p = node + _size;
					root()->r = nullptr;
				}
			}
			root()->update();
			node[_size].update();
			_root = node + _size++;
		}
	}
	void erase(T x){
		if(find(x)){
			Node* prv_root = root(),* prv_l = root()->l,* prv_r = root()->r;
			if(!prv_root->l){
				_root = prv_root->r;
			}
			else{
				prv_l->p = nullptr;
				prv_root->l = nullptr;
			}
			if(!prv_root->r){
				_root = prv_l;
			}
			else{
				prv_r->p = nullptr;
				prv_root->r = nullptr;
			}
			if(prv_l && prv_r){
				_root = prv_l;
				merge(prv_r);
			}
		}
	}

	template<class F>
	void tour(Node* v,F f,int d = 0,int dir = 0){
		if(v){
			tour(v->l,f,d+1,-1);
			f(v,d,dir);
			tour(v->r,f,d+1,1);
		}
	}
	void print_tree(){
		tour(root(),[&](Node* v,int d,int dir){
			std::cout << std::string(2*d,' ');
			if(dir == -1)std::cout << "/  ";
			if(dir == 0)std::cout << "-  ";
			if(dir == 1)std::cout << "\\  ";
			std::cout << v->val << '\n';
		});
	}
	void print(){
		std::cout << "{ ";
		tour(root(),[&](Node* v,int,int){
			std::cout << v->val << ", ";
		});
		std::cout << "}";
	}
};
std::ostream& operator<<(std::ostream& os,Set& rhs){ rhs.print(); return os; }
Set operator+=(Set& l,Set& r){
	r.tour(r.root(),[&](Set::Node* v,int,int){
		l.insert(v->val);
	});
	return l;
}
Set operator+(Set& l,Set& r){
	Set ret;
	l.tour(l.root(),[&](Set::Node* v,int,int){
		ret.insert(v->val);
	});
	r.tour(r.root(),[&](Set::Node* v,int,int){
		ret.insert(v->val);
	});
	return ret;
}
Set operator*=(Set& l,Set& r){
	r.tour(r.root(),[&](Set::Node* v,int,int){
		if(!l.find(v->val))l.erase(v->val);
	});
	return l;
}
Set operator*(Set& l,Set& r){
	Set ret;
	l.tour(l.root(),[&](Set::Node* v,int,int){
		if(r.find(v->val))ret.insert(v->val);
	});
	return ret;
}

Set::Node Set::node[MAX_SIZE];
int Set::_size = 0;


/**
* @title Splay Tree(set)
*/


#pragma endregion

int solve(){
	lin(q,k);
	Set s;
	while(q--){
		lint t,v; in(t);
		if(t==1){
			in(v);
			s.insert({v, q});
		}
		else{
			if(s.size()>=k){
				auto p = s.nth(k-1);
				out(p->val.first);
				s.erase(p->val);
			}
			else out(-1);
		}
	}
	return 0;
}

#pragma endregion

#pragma region main

int main(){
	solve();
}

#pragma endregion

//sub-EOF

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード