QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#36139#4270. Double AttendancemomoLRS0 10ms32084kbC++3.6kb2022-06-24 16:12:432022-06-24 16:12:44

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-24 16:12:44]
  • 评测
  • 测评结果:0
  • 用时:10ms
  • 内存:32084kb
  • [2022-06-24 16:12:43]
  • 提交

answer

#include<bits/stdc++.h>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define int long long
#define mod (1000000007)
// int mod;
#ifndef ONLINE_JUDGE
#pragma GCC optimize(2)
#endif
using namespace std;
namespace IO{
	inline int read(){
		int n=0;
		int s=1;
		char x;
		while((x=getchar())<'0'||x>'9')
			if(x=='-')
				s=-1;
		while(x>='0'&&x<='9'){
			n=(n<<1)+(n<<3)+(x^48),
			x=getchar();
		}
		return n*s;
	}
	void write(char x){
		putchar(x);
	}
	void write(const char *x){
		for(;*x;++x)
			putchar(*x);
	}
	void write(char *x){
		for(;*x;++x)
			putchar(*x);
	}
	void write(signed x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar('0'+x-x/10*10);
	}
	void write(long long x){
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar('0'+x-x/10*10);
	}
	void write(double x){
		printf("%lf",x);
	}
	template<typename type1,typename type2,typename ...typen>
	void write(type1 a1,type2 a2,typen ...an){
		write(a1);
		write(a2,an...);
	}
}// namespace IO
inline long long max(long long a,long long b){return a>b?a:b;}
inline long long min(long long a,long long b){return a>b?b:a;}
inline signed max(signed a,signed b){return a>b?a:b;}
inline signed min(signed a,signed b){return a>b?b:a;}
// stop
struct Node{
	int l,r;
	bool operator<(Node x)const{
		return l<x.l;
	}
}cl1[300001],cl2[300001];
map<int,int>mem[300001][2];
// #define wtf
signed main(){
	using namespace IO;
	// define int long long
	// mod = 1000000007
	#ifdef wtf
	string filename="name";
	freopen((filename+".in").c_str(),"r",stdin);
	freopen((filename+".out").c_str(),"w",stdout);
	#endif
	int n=read()+1,m=read(),k=read();
	cl1[1].l=0,cl1[1].r=1;
	for(int i=2;i<=n;i++){
		cl1[i].l=read(),cl1[i].r=read();
	}
	sort(cl1+1,cl1+n+1);
	for(int i=1;i<=m;i++){
		cl2[i].l=read(),cl2[i].r=read();
	}
	sort(cl2+1,cl2+m+1);
	int pos1=1,pos2=1;
	int ans=-1;
	mem[1][0][0]=0;
	for(int i=1,j=1;i<=n||j<=m;){
		if(j>m||(i<=n&&cl1[i].l<=cl2[j].l)){
			int maxm=-1;
			for(auto x:mem[i][0]){
				// cout<<0<<" "<<x.first<<" "<<x.second<<"\n";
				assert(x.first<cl1[i].r);
				maxm=max(maxm,x.second);
				while(pos2<=m&&cl2[pos2].r<=x.first+k)pos2++;
				if(pos2>m)continue;
				int t=max(cl2[pos2].l,x.first+k);
				if(t>=cl2[pos2].r)assert(0);
				mem[pos2][1][t]=max(mem[pos2][1][t],x.second+1);
			}
			ans=max(ans,maxm);
			if(maxm!=-1&&i<n)mem[i+1][0][cl1[i+1].l]=max(mem[i+1][0][cl1[i+1].l],maxm+1);
			i++;
			pos1=max(pos1,i);
		}
		else {
			int maxm=-1;
			for(auto x:mem[j][1]){
				assert(x.first<cl2[j].r);
				// cout<<1<<" "<<x.first<<" "<<x.second<<"\n";
				maxm=max(maxm,x.second);
				while(pos1<=n&&cl1[pos1].r<=x.first+k)pos1++;
				if(pos1>n)continue;
				int t=max(cl1[pos1].l,x.first+k);
				if(t>=cl1[pos1].r)assert(0);
				mem[pos1][0][t]=max(mem[pos1][0][t],x.second+1);
			}
			ans=max(maxm,ans);
			if(maxm!=-1&&j<m)mem[j+1][1][cl2[j+1].l]=max(mem[j+1][1][cl2[j+1].l],maxm+1);
			j++;
			pos2=max(pos2,j);
		}
	}
	write(ans);
	return 0;
}
/*
  ----  ----
   ----  ----
    ----  ----
    ----  ----
                       ----
               ----
         ----
    ----
                        ----
                 ----
          ----
   ----
                        ----
                 ----
            ----
      ----
                          ----
                ----
          ----
    ----
                          ----
                  ----
           ----
     ----

                     ----   ----

                     ----   ----

    ----   ----

    ----   ----

----------------------------------------
*/

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 3ms
memory: 31712kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

3

result:

ok single line: '3'

Test #2:

score: -5
Wrong Answer
time: 2ms
memory: 31788kb

input:

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

output:

3

result:

wrong answer 1st lines differ - expected: '4', found: '3'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 6
Accepted
time: 4ms
memory: 31684kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #105:

score: 0
Accepted
time: 10ms
memory: 31932kb

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: 0
Accepted
time: 3ms
memory: 32084kb

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:

4000

result:

ok single line: '4000'

Test #107:

score: 0
Accepted
time: 8ms
memory: 32012kb

input:

2000 2000 249875
965017250 965517000
73963000 74462750
242878500 243378250
148925500 149425250
747126250 747626000
384307750 384807500
655172250 655672000
278360750 278860500
899050250 899550000
496251750 496751500
92953500 93453250
677661000 678160750
828085750 828585500
297351250 297851000
5887055...

output:

4000

result:

ok single line: '4000'

Test #108:

score: -6
Wrong Answer
time: 7ms
memory: 32004kb

input:

2000 2000 499500
428 429
764235000 765234000
511488000 512487000
291 292
585414000 586413000
127 128
819 820
727 728
233766000 234765000
643 644
234 235
326 327
432 433
218781000 219780000
10989000 11988000
805194000 806193000
283716000 284715000
965034000 966033000
632367000 633366000
824 825
454 4...

output:

3998

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

0%