Submission #3019234
Source Code Expand
#include <cstdio>
#include <queue>
using namespace std;
const int N=200005;
const int INF=1e9;
int n,m;
int a[N][2];
inline int max(int x,int y){
return x>y?x:y;
}
inline int min(int x,int y){
return x<y?x:y;
}
namespace DINIC{/*{{{*/
const int S=3*N,M=23*N;
int flow_s,flow_t;
int dis[S],cur[S];
int h[S],tot;
struct Edge{
int v,f,next;
}e[M*2];
void init(int _flow_s,int _flow_t){
flow_s=_flow_s; flow_t=_flow_t;
tot=1;
}
void addEdge(int u,int v,int f){
//printf("%d %d %d\n",u,v,f);
e[++tot]=(Edge){v,f,h[u]}; h[u]=tot;
e[++tot]=(Edge){u,0,h[v]}; h[v]=tot;
}
queue<int> q;
bool bfs(){
for(int i=1;i<=flow_t;i++)
dis[i]=-1,cur[i]=h[i];
while(!q.empty()) q.pop();
q.push(flow_s);
dis[flow_s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=h[u],v;i;i=e[i].next)
if(e[i].f&&dis[v=e[i].v]==-1){
dis[v]=dis[u]+1;
if(v==flow_t) return true;
q.push(v);
}
}
return dis[flow_t]!=-1;
}
int dfs(int u,int flow){
if(u==flow_t)
return flow;
int get,res=0;
for(int i=cur[u],v;i&&flow;i=e[i].next)
if(e[i].f&&dis[v=e[i].v]==dis[u]+1){
get=dfs(v,min(flow,e[i].f));
e[i].f-=get;
e[i^1].f+=get;
if(e[i].f) cur[u]=i;
flow-=get;
res+=get;
}
if(!res) dis[u]=-1;
return res;
}
int solve(){
int res=0;
while(bfs())
res+=dfs(flow_s,INF);
return res;
}
}/*}}}*/
namespace SEG{/*{{{*/
const int S=N*4;
int rt,sz;
int ch[S][2];
void build(int &u,int l,int r){
u=++sz;
if(l==r){
DINIC::addEdge(u,DINIC::flow_t,1);
return;
}
int mid=(l+r)>>1;
build(ch[u][0],l,mid);
build(ch[u][1],mid+1,r);
DINIC::addEdge(u,ch[u][0],INF);
DINIC::addEdge(u,ch[u][1],INF);
}
void link(int u,int l,int r,int L,int R,int v){
if(L<=l&&r<=R){
DINIC::addEdge(v,u,1);
return;
}
int mid=(l+r)>>1;
if(R<=mid) link(ch[u][0],l,mid,L,R,v);
else if(mid<L) link(ch[u][1],mid+1,r,L,R,v);
else{
link(ch[u][0],l,mid,L,mid,v);
link(ch[u][1],mid+1,r,mid+1,R,v);
}
}
}/*}}}*/
void readData(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i][0],&a[i][1]);
a[i][0]=max(a[i][0],1);
a[i][1]=min(a[i][1],m);
}
}
void buildGraph(){
for(int i=1;i<=n;i++){
DINIC::addEdge(DINIC::flow_s,i,1);
SEG::link(SEG::rt,1,m,1,a[i][0],i);
SEG::link(SEG::rt,1,m,a[i][1],m,i);
}
}
int main(){
readData();
DINIC::init(n+2*m+1,n+2*m+2);
SEG::sz=n;
SEG::build(SEG::rt,1,m);
buildGraph();
int match=DINIC::solve();
printf("%d\n",n-match);
return 0;
}
Submission Info
Submission Time
2018-08-17 12:23:50+0900
Task
F - Exhausted?
User
RogerDTZ
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2629 Byte
Status
WA
Exec Time
2104 ms
Memory
114432 KB
Compile Error
./Main.cpp: In function ‘void readData()’:
./Main.cpp:104:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:106:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i][0],&a[i][1]);
^
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
TLE
2104 ms
95488 KB
02.txt
AC
1268 ms
76928 KB
03.txt
TLE
2104 ms
114432 KB
04.txt
TLE
2104 ms
114432 KB
05.txt
AC
26 ms
20096 KB
06.txt
TLE
2086 ms
85240 KB
07.txt
TLE
2104 ms
95488 KB
08.txt
TLE
2104 ms
114432 KB
09.txt
TLE
2104 ms
95488 KB
10.txt
AC
287 ms
50048 KB
11.txt
TLE
2104 ms
78976 KB
12.txt
AC
1680 ms
66432 KB
13.txt
TLE
2104 ms
64536 KB
14.txt
TLE
2104 ms
64408 KB
15.txt
TLE
2104 ms
81176 KB
16.txt
TLE
2104 ms
68480 KB
17.txt
TLE
2104 ms
114304 KB
18.txt
TLE
2104 ms
114304 KB
19.txt
TLE
2104 ms
101760 KB
20.txt
TLE
2104 ms
114304 KB
21.txt
AC
484 ms
44416 KB
22.txt
TLE
2104 ms
114304 KB
23.txt
AC
328 ms
25984 KB
24.txt
TLE
2104 ms
114304 KB
25.txt
WA
58 ms
41856 KB
26.txt
WA
51 ms
29440 KB
27.txt
AC
136 ms
44288 KB
28.txt
AC
117 ms
35840 KB
29.txt
AC
155 ms
44416 KB
30.txt
AC
155 ms
44416 KB
31.txt
TLE
2104 ms
114304 KB
32.txt
TLE
2104 ms
99712 KB
33.txt
TLE
2104 ms
114304 KB
34.txt
TLE
2104 ms
76800 KB
35.txt
TLE
2104 ms
66304 KB
36.txt
TLE
2104 ms
114304 KB
37.txt
AC
3 ms
8448 KB
38.txt
AC
2 ms
8448 KB
39.txt
AC
3 ms
8448 KB
40.txt
AC
2 ms
8448 KB
41.txt
AC
2 ms
8448 KB
42.txt
WA
2 ms
8448 KB
43.txt
AC
11 ms
26880 KB
44.txt
WA
2 ms
8448 KB
s1.txt
AC
2 ms
8448 KB
s2.txt
AC
2 ms
8448 KB
s3.txt
AC
2 ms
8448 KB
s4.txt
AC
3 ms
8448 KB