QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99215#6308. MagicExplodingKonjacTL 70ms6500kbC++174.4kb2023-04-21 17:11:402023-04-21 17:11:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-21 17:11:42]
  • 评测
  • 测评结果:TL
  • 用时:70ms
  • 内存:6500kb
  • [2023-04-21 17:11:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF

namespace FastIO
{

class FastIOBase
{
 protected:
#ifdef OPENIOBUF
	static const int BUFSIZE=1<<22;
	char buf[BUFSIZE+1];
	int buf_p=0;
#endif
	FILE *target;
 public:
#ifdef OPENIOBUF
	virtual void flush()=0;
#endif
	FastIOBase(FILE *f): target(f){}
	~FastIOBase()=default;
};

class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
 public:
	inline void flush()
		{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
 protected:
	inline void __putc(char x)
	{
#ifdef OPENIOBUF
		if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
		putc(x,target);
#endif
	}
	template<typename T>
	inline void __write(T x)
	{
		static char stk[64],*top;top=stk;
		if(x<0) return __putc('-'),__write(-x);
		do *(top++)=x%10,x/=10; while(x);
		for(;top!=stk;__putc(*(--top)+'0'));
	}
 public:
	FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
	inline void setTarget(FILE *f) { this->flush(),target=f; }
	~FastOutput(){ flush(); }
#else
	inline void setTarget(FILE *f) { target=f; }
#endif
	template<typename ...T>
	inline void writesp(const T &...x)
		{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
	template<typename ...T>
	inline void writeln(const T &...x)
		{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
	inline FastOutput &operator <<(char x)
		{ return __putc(x),*this; }
	inline FastOutput &operator <<(const char *s)
		{ for(;*s;__putc(*(s++)));return *this; }
	inline FastOutput &operator <<(const string &s)
		{ return (*this)<<s.c_str(); }
	template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
	inline FastOutput &operator <<(const T &x)
		{ return __write(x),*this; }
}qout;

class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
 public:
	inline void flush()
		{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
 protected:
	inline char __getc()
	{
#ifdef OPENIOBUF
		if(buf_p==BUFSIZE) flush();
		return buf[buf_p++];
#else
		return getc(target);
#endif
	}
 public:
#ifdef OPENIOBUF
	FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
	inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
	FastInput(FILE *f=stdin): FastIOBase(f){}
	inline void setTarget(FILE *f) { target=f; }
#endif
	inline char getchar() { return __getc(); }
	template<typename ...T>
	inline void read(T &...x)
		{ initializer_list<int>{(this->operator>>(x),0)...}; }
	inline FastInput &operator >>(char &x)
		{ while(isspace(x=__getc()));return *this; }
	template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
	inline FastInput &operator >>(T &x)
	{
		static char ch,sym;x=sym=0;
		while(isspace(ch=__getc()));
		if(ch=='-') sym=1,ch=__getc();
		for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
		return sym?x=-x:x,*this;
	}
	inline FastInput &operator >>(char *s)
	{
		while(isspace(*s=__getc()));
		for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
		return *s='\0',*this;
	}
	inline FastInput &operator >>(string &s)
	{
		char str_buf[(1<<8)+1],*p=str_buf;
		char *const buf_end=str_buf+(1<<8);
		while(isspace(*p=__getc()));
		for(s.clear(),p++;;p=str_buf)
		{
			for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
			*p='\0',s.append(str_buf);
			if(p!=buf_end) break;
		}
		return *this;
	}
}qin;

} // namespace FastIO
using namespace FastIO;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif

int n,ans,L[5005],R[5005],match[5005];
bitset<5005> g[5005];
bool bfs(int S)
{
	static int hd,tl,q[5005],pu[5005],pv[5005];
	bitset<5005> vis,ok;
	vis.reset(),ok.set(),q[hd=tl]=S;
	int T=0;
	while(hd<=tl)
	{
		int u=q[hd++];
		auto to=g[u]&ok;
		for(int v=to._Find_first(),w;v<=n;v=to._Find_next(v))
		{
			ok.reset(v);
			if(!(w=match[v])) { T=u,match[v]=u;goto gg; }
			else if(!vis.test(w)) q[++tl]=w,pu[w]=u,pv[w]=v,vis.set(w);
		}
	}
	gg: if(!T) return false;
	while(T!=S) match[pv[T]]=pu[T],T=pu[T];
	return true;
}
int main()
{
	qin>>n;
	for(int i=1;i<=n;i++) qin>>L[i]>>R[i];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		if(L[i]<L[j] && L[j]<R[i] && R[i]<R[j])
			g[i].set(j);
	for(int i=1;i<=n;i++) ans+=bfs(i);
	qout<<(2*n-ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3308kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 66ms
memory: 6436kb

input:

5000
7985 7987
42 46
1591 1593
407 410
6305 6306
1456 1457
5874 5875
7135 7137
7041 7046
6813 6815
8868 8871
665 666
4055 4056
9789 9796
7067 7068
4745 4746
5167 5171
1735 1737
2125 2128
1444 1447
1348 1352
6087 6090
1381 1384
1600 1601
5187 5190
2801 2802
8449 8450
9376 9377
4021 4024
2674 2676
490...

output:

8134

result:

ok 1 number(s): "8134"

Test #3:

score: 0
Accepted
time: 70ms
memory: 6500kb

input:

5000
3171 3172
4062 4064
4647 4651
3670 3673
7112 7114
9714 9717
3781 3789
8422 8426
457 460
5450 5454
7113 7122
6313 6320
9969 9973
828 832
6878 6892
4476 4483
892 903
251 259
6304 6315
130 134
9206 9215
2679 2686
9090 9091
8222 8228
9374 9375
2985 2989
3397 3401
4916 4918
6819 6821
883 889
2516 25...

output:

7047

result:

ok 1 number(s): "7047"

Test #4:

score: -100
Time Limit Exceeded

input:

5000
7269 7286
1979 1990
4225 4241
7866 7872
2052 2067
1508 1514
2366 2370
3488 3493
8979 8987
302 306
6730 6732
7704 7705
5528 5544
7420 7425
4705 4712
593 601
6662 6668
5228 5257
2008 2013
548 562
7949 7950
1017 1020
1025 1028
6 11
4722 4736
9945 9950
8368 8379
6781 6787
4558 4566
400 404
858 864
...

output:


result: