54472023-06-08 08:59:26mraronTom and Jerrycpp17Accepted 100/10011.354s44900 KiB
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#define ins insert

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

using ll = long long;
using ull = unsigned long long ;
using ld = long double ;
using str = string;
using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
    T val=0;
    char c;
    
    bool neg=false;
    while((c=gc()) && !(c>='0' && c<='9')) {
        neg|=c=='-';
    }

    do {
        val=(val*10)+c-'0';
    } while((c=gc()) && (c>='0' && c<='9'));

    return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)

int m,T;

struct pt {
    int xx,yy,ind;
};

void rot90(vector<pt>& lst) {
    for(auto& i:lst) {
        swap(i.xx, i.yy);
        i.xx=m+1-i.xx;
    }
}
 
 
struct ev {
    int x,typ,ind;
    int y1,y2;
    bool operator<(const ev& masik) {
        if(x==masik.x) {
            if(typ==masik.typ) {
                if(typ==0) return ind>masik.ind;
                else return ind<masik.ind;
            }
            return typ<masik.typ;
        }
        return x<masik.x;
    }
};

int escape(vector<pt> lst) {
    bool ok=false;
    int x=abs(lst[0].xx-1);
    
    vector<ev> evs;
    for(int i=0;i<sz(lst);++i) {
        if(abs(lst[i].xx-1)<=x) {
            evs.pb({max(1, lst[i].yy-x),0,i});
            evs.pb({min(lst[i].yy+x, m)+1,1,i});
        }
    }
    
    sort(all(evs));
    int cnt=0, act=0;
    for(auto i:evs) {
        if(i.typ==0) {
            if(i.ind==0) act=1;
            else cnt++;
        }else {
            if(i.ind==0) act=0;
            else cnt--;
        }
        
        if(act && cnt==0) {
            ok|=true;
        }
        
    
    }
    return ok?x:(int)2e9;
}


struct segtree {
	struct node {
		ll a = 1e9, lazy = 0; //default value
		
		node() {}
		node(ll a) : a(a) {}
		
		void apply(int L, int R, ll x) {
			a+=x;
		}

		node operator+(const node& b) {
			const node& a=*this;
			
			node res(min(a.a, b.a));
			return res;
		} 
	};

	void push(int ind, int L, int R) {
		if(tree[ind].lazy!=0) {
			tree[ind].apply(L, R, tree[ind].lazy);
			if(L!=R) {
				tree[2*ind].lazy+=tree[ind].lazy;
				tree[2*ind+1].lazy+=tree[ind].lazy;
			}
			
			tree[ind].lazy=0;
		}
	}

	inline void pull(int ind, int L, int R) {
		tree[ind]=tree[2*ind]+tree[2*ind+1];
	}

	int n;
	vector<node> tree;
	
	segtree(int n) : n(n) {
		tree.resize(4*n, node{});
	}
	
	void build() {
		build(1, 0, n-1);
	}
	
	void build(int ind, int L, int R, const vector<ll>& arr) {
		if(L==R) {
			tree[ind].apply(L, R, arr[L]);
		}else { 
			build(2*ind, L, (L+R)/2, arr);
			build(2*ind+1, (L+R)/2+1, R, arr);
			
			pull(ind, L, R);
		}
	}

	void build(int ind, int L, int R) {
		if(L!=R) { 
			build(2*ind, L, (L+R)/2);
			build(2*ind+1, (L+R)/2+1, R);
			
			pull(ind, L, R);
		}else {
            tree[ind]=node(0);
        }
	}
	
	node query(int i, int j) {
		return query(1, 0, n-1, i, j);
	}
	
	void incr(int i, int j, ll x) {
		incr(1, 0, n-1, i, j, x);
	}
	
	node query(int ind, int L, int R, int i, int j) {
		if(R<i||j<L) return node{};
		push(ind, L, R);
		
		if(i<=L && R<=j) {
			return tree[ind];
		}
		
		return query(2*ind, L, (L+R)/2, i, j)+query(2*ind+1, (L+R)/2+1, R, i, j);
	}
	
	
	void incr(int ind, int L, int R, int i, int j, ll x) {
		push(ind, L, R);
		if(R<i||j<L) return ;
		
		if(i<=L && R<=j) {
			tree[ind].lazy+=x;
			push(ind, L, R);
			return ;
		}
		
	
		incr(2*ind, L, (L+R)/2, i, j, x);
		incr(2*ind+1, (L+R)/2+1, R, i, j, x);

		pull(ind, L, R);
	}
};

bool can(vector<pt> lst, int x) {
    vector<ev> evs;
    for(int i=1;i<sz(lst);++i) {
        evs.push_back({max(1, lst[i].xx-x), -2,i, max(1, lst[i].yy-x)-1, min(m, lst[i].yy+x)-1});
        evs.push_back({min(m, lst[i].xx+x)+1,  2,i, max(1, lst[i].yy-x)-1, min(m, lst[i].yy+x)-1});
    }
    
    int L=max(1, lst[0].yy-x)-1, R=min(m, lst[0].yy+x)-1;
    evs.push_back({max(1, lst[0].xx-x), 3,0,L,R});
    evs.push_back({min(m, lst[0].xx+x)+1, -3,0,L,R});
    
    map<int,int> conv;
    vector<int> s;
    s.pb(0);
    s.pb(L);
    s.pb(R);
    s.pb(m-1);
    for(auto i:evs) {
        s.pb(i.y1);
        s.pb(i.y1+1);
        s.pb(i.y2);
        s.pb(i.y2+1);
    }
    sort(all(s));
    s.resize(distance(s.begin(), unique(all(s))));
    for(auto& i:evs) {
        i.y1=lower_bound(all(s), i.y1)-s.begin();
        i.y2=lower_bound(all(s), i.y2)-s.begin();
    }
    L=lower_bound(all(s), L)-s.begin();
    R=lower_bound(all(s), R)-s.begin();
    
    sort(all(evs));
    
    segtree st(s.size());
    st.build();
    
    bool ans=false, act=false;
    for(ev& e:evs) {        
        if(e.typ==-2) {
            st.incr(e.y1, e.y2, 1);
        }else if(e.typ==2) {
            st.incr(e.y1, e.y2, -1);
        }else {
            act^=1;
        }
            
        if(act) {
            ans|=st.query(L,R).a==0;
            if(ans) break ;
        }
    }
        
    return ans;
} 

int main() {
    IO;    
    cin>>m>>T;
    while(T--) {
        vector<pt> lst;
        lst.resize(1);
        cin>>lst[0].xx>>lst[0].yy;
        int n;
        cin>>n;
        lst.resize(n+1);
        for(int i=1;i<=n;++i) {
            cin>>lst[i].xx>>lst[i].yy;
            lst[i].ind=i;
        }
        
        int ans1=2e9;
        for(int i=0;i<4;++i) {
            ans1=min(escape(lst), ans1);
            rot90(lst);
        }
        
        if(ans1<2e9) {
            cout<<"ESCAPED "<<ans1<<"\n";
        }else {
            int ans2=0;
            for(int i=30;i>=0;i--) {
                int cans2=ans2+(1<<i);
                if(can(lst, cans2)) {
                    ans2=cans2;
                }
            }
            
            cout<<"CAUGHT "<<ans2+1<<"\n";
        }
    }
    return 0;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1760 KiB
subtask26/6
2Accepted83ms2072 KiB
3Accepted83ms2272 KiB
subtask310/10
4Accepted805ms2476 KiB
5Accepted792ms2696 KiB
subtask411/11
6Accepted41ms2952 KiB
7Accepted23ms3104 KiB
8Accepted64ms3332 KiB
9Accepted759ms3604 KiB
10Accepted46ms3572 KiB
11Accepted35ms3792 KiB
12Accepted149ms3740 KiB
13Accepted827ms3960 KiB
14Accepted1.527s4196 KiB
subtask513/13
15Accepted20ms4164 KiB
16Accepted3.691s5724 KiB
17Accepted4.166s18584 KiB
18Accepted25ms4400 KiB
19Accepted3.846s5816 KiB
20Accepted4.147s18648 KiB
subtask619/19
21Accepted46ms4548 KiB
22Accepted61ms4400 KiB
23Accepted83ms4544 KiB
24Accepted149ms4492 KiB
25Accepted184ms6728 KiB
26Accepted150ms4712 KiB
27Accepted187ms7084 KiB
subtask741/41
28Accepted61ms4984 KiB
29Accepted23ms4840 KiB
30Accepted64ms4856 KiB
31Accepted758ms5044 KiB
32Accepted46ms5156 KiB
33Accepted35ms5136 KiB
34Accepted149ms5208 KiB
35Accepted1.317s5100 KiB
36Accepted7.969s7292 KiB
37Accepted9.826s25700 KiB
38Accepted11.354s44900 KiB
39Accepted2.223s5252 KiB
40Accepted8.291s9740 KiB
41Accepted10.015s25900 KiB
42Accepted10.392s44596 KiB