Submission #27894497 - AtCoder Regular Contest 076

Contest Duration: 2017-06-24(Sat) 12:00 - 2017-06-24(Sat) 13:40 (local time) (100 minutes) Back to Home

Submission #27894497

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define N 200005
int n,m;
std::vector<int> V[N];
struct node{
  int mn,add;
}t[N<<2];
inline void psh(int p,int d){
  t[p].mn+=d,t[p].add+=d;
}
inline void pshd(int p){
  psh(p<<1,t[p].add),psh(p<<1|1,t[p].add);
  t[p].add=0;
}
inline void build(int p,int L,int R){
  if(L==R)
    return t[p].mn=m-L+1,void();
  int mid=(L+R)>>1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define N 200005

int n,m;

std::vector<int> V[N];

struct node{
	int mn,add;
}t[N<<2];
inline void psh(int p,int d){
	t[p].mn+=d,t[p].add+=d;
}
inline void pshd(int p){
	psh(p<<1,t[p].add),psh(p<<1|1,t[p].add);
	t[p].add=0;
}
inline void build(int p,int L,int R){
	if(L==R)
		return t[p].mn=m-L+1,void();
	int mid=(L+R)>>1;
	build(p<<1,L,mid),build(p<<1|1,mid+1,R);
	t[p].mn=std::min(t[p<<1].mn,t[p<<1|1].mn);
}
inline void add(int p,int L,int R,int l,int r){
	if(L>r||R<l)
		return;
	if(l<=L&&R<=r)
		return psh(p,-1);
	pshd(p);
	int mid=(L+R)>>1;
	add(p<<1,L,mid,l,r),add(p<<1|1,mid+1,R,l,r);
	t[p].mn=std::min(t[p<<1].mn,t[p<<1|1].mn);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		V[l].push_back(r);
	}
	build(1,1,m+1);
	int ans=m-n;
	for(int i=0;i<=m;i++){
		for(auto j:V[i])
			add(1,1,m+1,1,j);
		ans=std::min(ans,i+t[1].mn);
	}
	printf("%d\n",-ans);
}

Submission Info

Submission Time	2021-12-13 08:52:01
Task	F - Exhausted?
User	Y25t
Language	C++ (GCC 9.2.1)
Score	1000
Code Size	985 Byte
Status	AC
Exec Time	117 ms
Memory	16092 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:37:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
./Main.cpp:40:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

1000 / 1000

Status

× 4

× 48

Set Name	Test Cases
Sample	s1.txt, s2.txt, s3.txt, s4.txt
All	01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s1.txt, s2.txt, s3.txt, s4.txt

Case Name	Status	Exec Time	Memory
01.txt	AC	96 ms	15296 KiB
02.txt	AC	73 ms	15156 KiB
03.txt	AC	110 ms	16092 KiB
04.txt	AC	117 ms	16068 KiB
05.txt	AC	17 ms	10680 KiB
06.txt	AC	82 ms	15276 KiB
07.txt	AC	91 ms	12788 KiB
08.txt	AC	117 ms	16024 KiB
09.txt	AC	91 ms	12920 KiB
10.txt	AC	45 ms	13908 KiB
11.txt	AC	72 ms	13656 KiB
12.txt	AC	55 ms	13620 KiB
13.txt	AC	63 ms	10068 KiB
14.txt	AC	66 ms	10076 KiB
15.txt	AC	69 ms	13656 KiB
16.txt	AC	58 ms	12180 KiB
17.txt	AC	102 ms	15636 KiB
18.txt	AC	94 ms	15640 KiB
19.txt	AC	85 ms	15320 KiB
20.txt	AC	91 ms	15644 KiB
21.txt	AC	33 ms	13136 KiB
22.txt	AC	93 ms	15644 KiB
23.txt	AC	19 ms	9776 KiB
24.txt	AC	90 ms	15648 KiB
25.txt	AC	39 ms	12632 KiB
26.txt	AC	34 ms	10448 KiB
27.txt	AC	58 ms	12960 KiB
28.txt	AC	57 ms	10756 KiB
29.txt	AC	47 ms	12816 KiB
30.txt	AC	49 ms	12792 KiB
31.txt	AC	99 ms	15564 KiB
32.txt	AC	85 ms	15208 KiB
33.txt	AC	95 ms	15688 KiB
34.txt	AC	64 ms	14636 KiB
35.txt	AC	52 ms	13988 KiB
36.txt	AC	88 ms	15628 KiB
37.txt	AC	7 ms	8416 KiB
38.txt	AC	9 ms	8308 KiB
39.txt	AC	7 ms	8420 KiB
40.txt	AC	7 ms	8460 KiB
41.txt	AC	8 ms	8424 KiB
42.txt	AC	11 ms	8412 KiB
43.txt	AC	15 ms	12384 KiB
44.txt	AC	8 ms	8528 KiB
s1.txt	AC	7 ms	8288 KiB
s2.txt	AC	10 ms	8508 KiB
s3.txt	AC	11 ms	8532 KiB
s4.txt	AC	13 ms	8304 KiB