QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#35664#4270. Double Attendancep_b_p_b0 12ms42936kbC++175.8kb2022-06-17 21:20:012022-06-17 21:20:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-17 21:20:02]
  • 评测
  • 测评结果:0
  • 用时:12ms
  • 内存:42936kb
  • [2022-06-17 21:20:01]
  • 提交

answer

#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define pll pair<ll,ll>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 333333
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cerr<<clock()/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n,m; ll K;
struct hh{ll l,r;bool operator < (const hh &a) const {return l<a.l;}}a[sz],b[sz];
int opA[sz],opB[sz];
int idA[sz][2],idB[sz][2],cc;
vector<pii>V[sz<<2];
int dp[sz<<2];

// x 属于哪个线段;如果哪个都不属于就往前走 
int findA(ll x){int p=upper_bound(a+1,a+n+1,(hh){x,x})-a-1;if (p!=0&&a[p].r>=x) return p;return p+1;}
int findB(ll x){int p=upper_bound(b+1,b+m+1,(hh){x,x})-b-1;if (p!=0&&b[p].r>=x) return p;return p+1;}

int __CUR;
pll _tr[2][sz<<2];
#define tr _tr[__CUR]
#define ls k<<1
#define rs k<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
void build(int k,int l,int r,hh *a)
{
	if (l==r) return tr[k]=MP(a[l].l-2ll*K*l,a[l].r-2ll*K*l),void();
	int mid=(l+r)>>1;
	build(lson,a),build(rson,a);
	tr[k]=MP(max(tr[ls].fir,tr[rs].fir),min(tr[ls].sec,tr[rs].sec));
}
int query(int k,int l,int r,int st,ll x)
{
	if (r<st) return -1;
	if (l==r) return x>=tr[k].fir&&x<=tr[k].sec?-1:l;
	int mid=(l+r)>>1;
	int res=query(lson,st,x);
	if (res!=-1) return res;
	return query(rson,st,x);
}

void work()
{
	__CUR=0; build(1,1,n+1,a);
	__CUR=1; build(1,1,m+1,b);
	auto GO=[](int i,int j,int l,int r,int del,int c,ll x)
	{
//		cerr<<l<<' '<<r<<'\n';
			rep(_,1,1) // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!
			{
//				if (_>8)
//				{
//					cerr<<i<<' '<<j<<'\n';
//				}
				x+=K;
				if (b[r].l>x||b[r].r<x)
				{
					r=findB(x);
					if (b[r].l<x) c+=(r!=del),++r;
					V[idA[i][j]].push_back(MP(idB[r][opB[r]==l],c+1));
					break;
				}
				assert(r<=m);
				V[idA[i][j]].push_back(MP(idB[r+1][opB[r+1]==l],c+(r!=del)+1));
				c+=(r!=del); del=l;
				++l;
				x+=K;
				if (a[l].l>x||a[l].r<x)
				{
					l=findA(x);
					if (a[l].l<x) c+=(l!=del),++l;
					V[idA[i][j]].push_back(MP(idA[l][opA[l]==r],c+1));
					break;
				}
				assert(l<=n);
				V[idA[i][j]].push_back(MP(idA[l+1][opA[l+1]==r],c+(l!=del)+1));
				c+=(l!=del); del=r;
				++r;
			}
	};
	rep(i,1,n)
	{
		ll x=a[i].l;
		int t=findB(x+K);
		rep(j,0,1)
		{
			int l=i,r=t,del=(j?opA[i]:0),c=0;
			GO(i,j,l,r,del,c,x);
		}
		continue; // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
		__CUR=0; int af=query(1,1,n+1,i+1,x+2ll*K-2ll*(i+1)*K);
		__CUR=1; int bf=query(1,1,m+1,t,x+K-2ll*t*K);
		if (min(af-i-1,bf-t)<=6) continue;
		rep(j,0,1)
		{
			int l=i,r=t,del=(j?opA[i]:0),c=(del!=t);
			int k=min(af-i-1,bf-t)-3; l+=k,r+=k,c+=2*k-1,x+=2*k*K; del=r-1;
//			cerr<<l<<' '<<r<<'\n';
			GO(i,j,l,r,del,c,x);
		}
	}
}

void DP()
{
	static pii id[sz<<2]; int cc=0;
	rep(i,1,n+1) rep(j,0,1) id[++cc]=MP(a[i].l,idA[i][j]);
	rep(i,1,m+1) rep(j,0,1) id[++cc]=MP(b[i].l,idB[i][j]);
	sort(id+1,id+cc+1);
	static int pre[sz]; rep(i,1,cc) pre[id[i].sec]=i;
	memset(dp,~0x3f,sizeof(dp));
	dp[idA[1][0]]=1;
	rep(i,1,cc) for (auto p:V[id[i].sec]) chkmax(dp[p.fir],dp[id[i].sec]+p.sec);
}

int main()
{
	file();
	read(n,m,K);
	rep(i,1,n) read(a[i].l,a[i].r),--a[i].r;
	rep(i,1,m) read(b[i].l,b[i].r),--b[i].r;
	sort(a+1,a+n+1),sort(b+1,b+m+1);
	int added=0;
	if (a[1].l!=0) { added=1; ++n; drep(i,n,2) a[i]=a[i-1]; a[1]=hh{0,0}; }
	a[n+1]=b[m+1]=hh{int(2e9)+1,int(2e9)+1};
	rep(i,1,n+1) opA[i]=findB(a[i].l),opA[i]=((opA[i]!=-1&&b[opA[i]].l<=a[i].l)?opA[i]:m+i+1);
	rep(i,1,m+1) opB[i]=findA(b[i].l),opB[i]=((opB[i]!=-1&&a[opB[i]].l<=b[i].l)?opB[i]:n+i+1);
	rep(i,1,n+1) rep(j,0,1) idA[i][j]=++cc; rep(i,1,m+1) rep(j,0,1) idB[i][j]=++cc;
	
	// 无脑往前走 
	rep(i,1,n) rep(j,0,1) V[idA[i][j]].push_back(MP(idA[i+1][j&&opA[i]==opA[i+1]],1));
	rep(i,1,m) rep(j,0,1) V[idB[i][j]].push_back(MP(idB[i+1][j&&opB[i]==opB[i+1]],1));
	
	// 向对面跳
	work();
	{
		int _=max(n+1,m+1);
		rep(i,1,_) swap(a[i],b[i]),swap(opA[i],opB[i]);
		rep(i,1,_) rep(j,0,1) swap(idA[i][j],idB[i][j]);
		swap(n,m);
	}
	work();
	{
		int _=max(n+1,m+1);
		rep(i,1,_) swap(a[i],b[i]),swap(opA[i],opB[i]);
		rep(i,1,_) rep(j,0,1) swap(idA[i][j],idB[i][j]);
		swap(n,m);
	}
	
	DP();
	cout<<dp[idA[n+1][0]]-1-added;
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 4ms
memory: 42220kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 9ms
memory: 42132kb

input:

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 9ms
memory: 42128kb

input:

10 10 5
4 9
43 48
69 70
70 72
52 67
75 83
100 103
103 1501
10 27
28 40
5 7
27 29
30 39
40 42
42 45
67 80
0 5
45 59
10 20
22 23

output:

18

result:

ok single line: '18'

Test #4:

score: 0
Accepted
time: 5ms
memory: 42124kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 7ms
memory: 41984kb

input:

1 10 2
1 2000
4 5
10 11
7 8
3 4
9 10
1 2
2 3
8 9
6 7
5 6

output:

10

result:

ok single line: '10'

Test #6:

score: -5
Wrong Answer
time: 4ms
memory: 42132kb

input:

10 10 90
1440 1620
0 180
1080 1260
900 1080
180 360
720 900
540 720
360 540
1620 1800
1260 1440
1170 1350
990 1170
1530 1710
1350 1530
90 270
450 630
270 450
630 810
810 990
1710 1890

output:

15

result:

wrong answer 1st lines differ - expected: '20', found: '15'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 6
Accepted
time: 3ms
memory: 42212kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #105:

score: 0
Accepted
time: 12ms
memory: 42452kb

input:

1 2000 2
999999996 1000000000
336 337
502 503
1906 1907
963 964
1351 1352
1795 1796
1510 1511
304 305
1930 1931
1735 1736
1469 1470
338 339
813 814
182 183
209 210
321 322
849 850
721 722
394 395
889 890
1758 1759
1440 1441
560 561
1470 1471
1916 1917
793 794
1366 1367
158 159
1602 1603
214 215
1119...

output:

2000

result:

ok single line: '2000'

Test #106:

score: -6
Wrong Answer
time: 12ms
memory: 42936kb

input:

2000 2000 249875
608195750 608695500
88455750 88955500
579210250 579710000
817091250 817591000
527736000 528235750
52473750 52973500
89955000 90454750
184407750 184907500
668165750 668665500
24487750 24987500
466266750 466766500
471764000 472263750
212393750 212893500
250874500 251374250
939530000 9...

output:

3000

result:

wrong answer 1st lines differ - expected: '4000', found: '3000'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%