#841279 (C++14) No.2220 Range Insert & Point Mex

提出ソース

結果

問題	No.2220 Range Insert & Point Mex
ユーザー	tokitsukaze
提出日時	2023-02-17 22:48:06
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	241 ms / 2,000 ms
コード長	5,096 bytes
コンパイル時間	3,870 ms
コンパイル使用メモリ	209,272 KB
実行使用メモリ	18,736 KB
最終ジャッジ日時	2024-07-21 12:51:39
合計ジャッジ時間	9,231 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	150 ms 14,004 KB
testcase_14	AC	146 ms 14,000 KB
testcase_15	AC	151 ms 13,996 KB
testcase_16	AC	154 ms 14,004 KB
testcase_17	AC	149 ms 14,004 KB
testcase_18	AC	151 ms 14,004 KB
testcase_19	AC	148 ms 14,000 KB
testcase_20	AC	241 ms 15,536 KB
testcase_21	AC	239 ms 15,536 KB
testcase_22	AC	233 ms 15,536 KB
testcase_23	AC	93 ms 14,004 KB
testcase_24	AC	88 ms 13,872 KB
testcase_25	AC	62 ms 8,748 KB
testcase_26	AC	84 ms 14,004 KB
testcase_27	AC	74 ms 14,124 KB
testcase_28	AC	11 ms 6,944 KB
testcase_29	AC	12 ms 6,940 KB
testcase_30	AC	11 ms 6,940 KB
testcase_31	AC	96 ms 18,736 KB
testcase_32	AC	42 ms 7,340 KB
testcase_33	AC	55 ms 7,344 KB
testcase_34	AC	63 ms 9,260 KB
testcase_35	AC	73 ms 9,264 KB
testcase_36	AC	87 ms 12,720 KB
testcase_37	AC	106 ms 12,592 KB
testcase_38	AC	89 ms 11,680 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
namespace fastIO{
	#define BUF_SIZE 100000
	#define OUT_SIZE 100000
	//fread->read
	bool IOerror=0;
	//inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;} 
	inline char nc(){
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
		if(p1==pend){
			p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
			if(pend==p1){IOerror=1;return -1;}
		}
		return *p1++;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	template<class T> inline bool read(T &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(sign)x=-x;
		return true;
	}
	inline bool read(double &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(ch=='.'){
			double tmp=1; ch=nc();
			for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
		}
		if(sign)x=-x;
		return true;
	}
	inline bool read(char *s){
		char ch=nc();
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
		*s=0;
		return true;
	}
	inline bool read_line(char *s){
		char ch=nc();
		for(;blank(ch);ch=nc());
		if(IOerror)return false;
		for(;ch!='\n'&&!IOerror;ch=nc())*s++=ch;
		*s=0;
		return true;
	}
	inline bool read(char &c){
		for(c=nc();blank(c);c=nc());
		if(IOerror){c=-1;return false;}
		return true; 
	}
	template<class T,class... U>bool read(T& h,U&... t){return read(h)&&read(t...);}
	#undef OUT_SIZE
	#undef BUF_SIZE
};
using namespace fastIO;
/************* debug begin *************/
string to_string(string s){return '"'+s+'"';}
string to_string(const char* s){return to_string((string)s);}
string to_string(const bool& b){return(b?"true":"false");}
template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template<class A>string to_string(const vector<A> v){
	int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
	return res;
}
void debug_out(){puts("");}
template<class T,class... U>void debug_out(const T& h,const U&... t){cout<<" "<<to_string(h);debug_out(t...);}
#ifdef tokitsukaze 
#define debug(...) cout<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__);
#else
#define debug(...) 233;
#endif
/*************  debug end  *************/
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int,ll> PIL;
typedef pair<ll,int> PLI;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<string> VS;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VS> VVS;
typedef vector<VPII> VVPII;
/************* define end  *************/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/********* gp_hash_table end  **********/
void read(int *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(ll *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void read(double *x,int l,int r){for(int i=l;i<=r;i++) read(x[i]);}
void println(VI x){for(int i=0;i<sz(x);i++) printf("%d%c",x[i]," \n"[i==sz(x)-1]);}
void println(VL x){for(int i=0;i<sz(x);i++) printf("%lld%c",x[i]," \n"[i==sz(x)-1]);}
void println(int *x,int l,int r){for(int i=l;i<=r;i++) printf("%d%c",x[i]," \n"[i==r]);}
void println(ll *x,int l,int r){for(int i=l;i<=r;i++) printf("%lld%c",x[i]," \n"[i==r]);}
/*************** IO end  ***************/
void go();
int main(){
	#ifdef tokitsukaze
		freopen("TEST.txt","r",stdin);
	#endif
	go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=3e5+10;
const ll mod=998244353;
/*********************************  head  *********************************/
struct node
{
	int l,r,x;
	friend bool operator<(node a,node b)
	{
		return a.l<b.l;
	}
};
void go()
{
	int n,q,i,j,l,r,x;
	while(read(n))
	{
		vector<node> qst;
		for(i=1;i<=n;i++)
		{
			read(l,r,x);
			qst.pb({l,r,x});
		}
		sort(all(qst));
		multiset<int> s;
		s.insert(INF);
		multiset<PII> now;
		set<int> ans;
		for(i=0;i<=n+5;i++) ans.insert(i);
		j=0;
		read(q);
		for(i=1;i<=q;i++)
		{
			read(x);
			while(j<sz(qst)&&qst[j].l<=x)
			{
				s.insert(qst[j].x);
				now.insert(MP(qst[j].r,qst[j].x));
				ans.erase(qst[j].x);
				j++;
			}
			while(sz(now) && (*now.begin()).fi<x)
			{
				s.erase(s.find((*now.begin()).se));
				if(s.find((*now.begin()).se)==s.end())
				{
					ans.insert((*now.begin()).se);
				}
				now.erase(now.begin());
			}
			printf("%d\n",*ans.begin());
		}
	}
}

yukicoder

結果

テストケース

ソースコード