#include "bits/stdc++.h"
//#include "game.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 3e5 + 5;
const int BL = 600;
vector<int> v[N],g[N];
bool vis[N],vis2[N];
int n,m,k,out[N],in[N],bin[N],bout[N];
bool ok=0;
void upd_in(int a,int val){
if(in[a]<val || ok || bin[a]>bout[a]) return;
in[a]=min(in[a],val);
bin[a]=min(bin[a],val/BL);
if(in[a]<out[a] || bin[a]<bout[a]){
ok=1;
return;
}
if(in[a]==out[a] && a>=k){
ok=1;
return;
}
for(int x:g[a]){
if(bin[x]!=bin[a]) continue;
if(val<in[x]) upd_in(x,val);
}
}
void upd_out(int a,int val){
if(out[a]>val || ok || bin[a]>bout[a]) return;
out[a]=max(out[a],val);
bout[a]=max(bout[a],val/BL);
if(in[a]<out[a] || bin[a]<bout[a]){
ok=1;
return;
}
if(in[a]==out[a] && a>=k){
ok=1;
return;
}
for(int x:v[a]){
if(bin[x]!=bin[a]) continue;
if(out[x]<val) upd_out(x,val);
}
}
void upd_bin(int a,int val,int real){
if(bin[a]<=val || ok) return;
bin[a]=val;
in[a]=min(in[a],real);
if(bin[a]<bout[a] || in[a]<out[a]){
ok=1;
return;
}
if(in[a]==out[a] && a>=k){
ok=1;
return;
}
if(bin[a]==bout[a]){
upd_in(a,in[a]);
upd_in(in[a],in[a]);
}
if(bin[a]<bout[a] || in[a]<out[a]){
ok=1;
return;
}
if(in[a]==out[a] && a>=k){
ok=1;
return;
}
for(int x:g[a]){
if(bin[x]>val) upd_bin(x,val,in[a]);
else if(bin[x]==val) upd_in(x,in[a]);
}
}
void upd_bout(int a,int val,int real){
if(bout[a]>=val || ok) return;
bout[a]=val;
out[a]=max(out[a],real);
if(bin[a]<bout[a] || in[a]<out[a]){
ok=1;
return;
}
if(in[a]==out[a] && a>=k){
ok=1;
return;
}
if(bin[a]==bout[a]){
upd_out(a,out[a]);
upd_out(out[a],out[a]);
}
if(bin[a]<bout[a] || in[a]<out[a]){
ok=1;
return;
}
if(in[a]==out[a] && a>=k){
ok=1;
return;
}
for(int x:v[a]){
if(bout[x]<val) upd_bout(x,val,out[a]);
else if(bout[x]==val) upd_out(x,out[a]);
}
}
void init(int _n,int _k){
n=_n,k=_k;
for(int i=1;i<k;i++){
v[i-1].push_back(i);
g[i].push_back(i-1);
}
fill(bout,bout+N,-1);
fill(bin,bin+N,k);
fill(out,out+N,-1);
fill(in,in+N,k);
for(int i=0;i<k;i++) bin[i]=bout[i]=i/BL;
for(int i=0;i<k;i++) in[i]=out[i]=i;
}
int add_teleporter(int a, int b){
if(a==b && a<k) ok=1;
if(a<k && b<k && a>b) ok=1;
v[a].push_back(b);
g[b].push_back(a);
upd_bout(b,bout[a],out[a]);
upd_bin(a,bin[b],in[b]);
upd_in(a,in[b]);
upd_out(b,out[a]);
return ok;
}
void _(){
cin >> n >> m >> k;
for(int i=1;i<k;i++){
v[i-1].push_back(i);
g[i].push_back(i-1);
}
init(n,k);
for(int i=1;i<=m;i++){
int a,b;
cin >> a >> b;
cout << add_teleporter(a,b) << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc7Gjh4F.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuTn5WF.o:game.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc7Gjh4F.o: in function `main':
stub.cpp:(.text.startup+0x64): undefined reference to `init(int, int)'
/usr/bin/ld: stub.cpp:(.text.startup+0xda): undefined reference to `add_teleporter(int, int)'
collect2: error: ld returned 1 exit status
