Submission #3019250
Source Code Expand
#include<bits/stdc++.h>
//#define empty (h<t)
//#define front (q[h])
//#define pop h++
//#define push(x) q[t++]=(x)
#define M 600005
#define INF 19260817
using namespace std;
int n,m;
struct edge{int u,v,next;}e[M*14]={0}; int head[M]={0},cur[M]={0},use=0;
void add(int x,int y,int z){e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use++;}
void ADD(int x,int y,int z){add(x,y,z); add(y,x,0);}
int dis[M]={0},S,T;
queue<int> q;
bool bfs(){
memset(dis,0,sizeof(dis));
q.push(S); dis[S]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=head[u];~i;i=e[i].next)
if(dis[e[i].u]==0&&e[i].v){
dis[e[i].u]=dis[u]+1;
q.push(e[i].u);
}
}
return dis[T];
}
int dfs(int x,int flow){
if(x==T) return flow;
int sum=0;
for(int i=cur[x];~i;i=e[i].next){
if(!e[i].v) continue;
if(dis[e[i].u]!=dis[x]+1) continue;
int k=dfs(e[i].u,min(e[i].v,flow));
sum+=k; e[i].v-=k;
e[i^1].v+=k; flow-=k;
if(!flow) return sum;
if(e[i].v) cur[x]=i;
}
return sum;
}
int dinic(){
int ans=0,k;
while(bfs()){
memcpy(cur,head,sizeof(cur));
ans+=dfs(S,INF);
}
return ans;
}
struct seg{
int l,r,id;
}a[M<<2]={0}; int cnt=0;
void build(int x,int l,int r){
a[x].id=++cnt; a[x].l=l; a[x].r=r;
if(l==r) return ADD(a[x].id,T,1);
int mid=(l+r)>>1;
build(x<<1,l,mid); build(x<<1|1,mid+1,r);
ADD(a[x].id,a[x<<1].id,INF);
ADD(a[x].id,a[x<<1|1].id,INF);
}
void updata(int x,int l,int r,int id){
if(l<=a[x].l&&a[x].r<=r) return ADD(id,a[x].id,1);
int mid=(a[x].l+a[x].r)>>1;
if(l<=mid) updata(x<<1,l,r,id);
if(mid<r) updata(x<<1|1,l,r,id);
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) ADD(S,i,1);
cnt=m; T=++cnt; build(1,1,n);
for(int i=1;i<=m;i++){
int l,r; scanf("%d%d",&l,&r);
if(1<=l)
updata(1,1,l,i);
if(r<=n)
updata(1,r,n,i);
}
if(cnt>400000)
printf("%d\n",max(0,m-n));
else cout<<m-dinic()<<endl;
}
Submission Info
Submission Time
2018-08-17 12:28:19+0900
Task
F - Exhausted?
User
AlphaINF
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1972 Byte
Status
WA
Exec Time
2104 ms
Memory
112896 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:71:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&m,&n);
^
./Main.cpp:75:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int l,r; scanf("%d%d",&l,&r);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1000
Status
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
129 ms
98560 KB
02.txt
AC
92 ms
78080 KB
03.txt
AC
151 ms
112896 KB
04.txt
AC
153 ms
112896 KB
05.txt
AC
391 ms
22912 KB
06.txt
AC
109 ms
86272 KB
07.txt
TLE
2104 ms
95488 KB
08.txt
AC
151 ms
112896 KB
09.txt
TLE
2104 ms
97536 KB
10.txt
AC
49 ms
51456 KB
11.txt
WA
98 ms
78080 KB
12.txt
WA
75 ms
65792 KB
13.txt
TLE
2104 ms
63256 KB
14.txt
TLE
2104 ms
63256 KB
15.txt
WA
99 ms
80128 KB
16.txt
TLE
2104 ms
68400 KB
17.txt
AC
151 ms
112896 KB
18.txt
AC
151 ms
112896 KB
19.txt
WA
132 ms
100608 KB
20.txt
WA
153 ms
112896 KB
21.txt
AC
36 ms
43264 KB
22.txt
WA
152 ms
112896 KB
23.txt
AC
499 ms
26624 KB
24.txt
AC
156 ms
112896 KB
25.txt
WA
35 ms
33024 KB
26.txt
AC
30 ms
21376 KB
27.txt
AC
40 ms
39168 KB
28.txt
AC
37 ms
28928 KB
29.txt
AC
50 ms
39168 KB
30.txt
AC
50 ms
39168 KB
31.txt
WA
157 ms
112896 KB
32.txt
AC
134 ms
100608 KB
33.txt
AC
157 ms
112896 KB
34.txt
AC
101 ms
78080 KB
35.txt
AC
77 ms
69888 KB
36.txt
AC
150 ms
112896 KB
37.txt
AC
4 ms
10496 KB
38.txt
AC
4 ms
10496 KB
39.txt
AC
4 ms
10496 KB
40.txt
AC
4 ms
10496 KB
41.txt
AC
4 ms
10496 KB
42.txt
AC
3 ms
8448 KB
43.txt
WA
13 ms
30976 KB
44.txt
AC
3 ms
8448 KB
s1.txt
AC
4 ms
10496 KB
s2.txt
AC
4 ms
10496 KB
s3.txt
AC
4 ms
10496 KB
s4.txt
AC
4 ms
10496 KB