Submission #1261942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261942		_rain_	New Home (APIO18_new_home)	C++20	12 / 100	5095 ms	126188 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))

template<class T1,class T2>	
	bool maximize(T1 &a,T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1,class T2>	
	bool minimize(T1 &a,T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T1>
	void compress(vector<T1>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1,class T2>
	int Find(vector<T1>&data,T2 x){
		return upper_bound(data.begin() , data.end() , x) - data.begin();
	}

const int N = (int) 3e5;
const int inf = (int)1e9;
	int n , k , q;
	int x[N + 2] , t[N + 2] , a[N + 2] , b[N + 2];
	
	
	struct Question{
		int l,y;
		void read(){
			cin >> l >> y;
		}
	} queri[N + 2];
	
namespace subtask1{
	bool check(){
		return k <= 400;
	}
	
	const int MAXN = (int) N * 3;
		vector<int>nen;
		vector<pair<int,int>>open[MAXN + 2] , close[MAXN + 2] , ask[MAXN + 2];
		
	multiset<int>st[N+2];
	int cnt[MAXN + 2] = {};
	int ans[N + 2] = {};
		
	void main_code(){
		for(int i = 1; i <= n; ++i) {
			nen.push_back(a[i]) , 
			nen.push_back(b[i]);
		}
		for(int i = 1; i <= q; ++i) nen.push_back(queri[i].y);
		compress(nen);
		for(int i = 1; i <= n; ++i){
			a[i] = Find(nen , a[i]) , b[i] = Find(nen , b[i]);
			open[a[i]].push_back({x[i] , t[i]});
			close[b[i]].push_back({x[i] , t[i]});
		}
		for(int i = 1; i <= q; ++i){
			queri[i].y = Find(nen , queri[i].y);
			ask[queri[i].y].push_back({queri[i].l , i});
			ans[i] = 0;
		}
		
		int full = 0;
				
		for(int i = 1; i <= sz(nen); ++i){
			for(auto x : open[i]) {
				//... setalize
					full -= (cnt[x.second] > 0);
					cnt[x.second]++;
					full += (cnt[x.second] > 0);

				st[x.second].insert(x.first);
			}
			for(auto x : ask[i]){
				if (full != k) ans[x.second] = -1;
				else {
					for(int j = 1; j <= k; ++j){
						auto t1 = st[j].lower_bound(x.first);
						int res = inf;
						if (t1!=st[j].end()) minimize(res , abs(*t1 - x.first));
						if (t1!=st[j].begin()){
							--t1;
							minimize(res , abs(*t1 - x.first));
						}
						maximize(ans[x.second] , res);
					}
				}
			}
			for(auto x : close[i]) {
				//... setalize
					full -= (cnt[x.second] > 0);
					cnt[x.second]--;
					full += (cnt[x.second] > 0);
					
				st[x.second].erase(st[x.second].find(x.first));
			}
		}
		for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
	}
}
	
namespace subtask2{
	bool check(){
		for(int i = 1; i <= n; ++i) if (a[i] != 1 || b[i] != (int)1e8) return false;
		return true;
	}
	
	vector<int>nen;
	
	class IT{
		public:
			vector<int> st_max , st_min;
			vector<int> lazy_max , lazy_min;
			void load_size(int n){
				st_max = lazy_max = vector<int>(n * 4 + 2 , 0);
				st_min = lazy_min = vector<int>(n * 4 + 2 , inf);
			}
			
			void pushdown(int id){
				int &t1 = lazy_max[id] , &t2 = lazy_min[id];
					maximize(st_max[id * 2] , t1);
					maximize(st_max[id * 2 + 1] , t1);
					
					minimize(st_min[id * 2] , t2);
					minimize(st_min[id * 2 + 1] , t2);
					
					maximize(lazy_max[id * 2] , t1);
					maximize(lazy_max[id * 2 + 1] , t1);
					
					minimize(lazy_min[id * 2] , t2);
					minimize(lazy_min[id * 2 + 1] , t2);
				return;
			}
			
			void update(int id , int l , int r , int u , int v , int val){
				if (l > v || r < u) return ;
				if (u <= l && r <= v){
					st_max[id] = max(st_max[id] , val);
					st_min[id] = min(st_min[id] , val);
					
					lazy_max[id] = max(lazy_max[id] , val);
					lazy_min[id] = min(lazy_min[id] , val);
					return;
				}
				int m = (l + r) / 2;
				pushdown(id);
				update(id * 2 , l , m , u , v , val);
				update(id * 2 + 1 , m + 1 , r , u , v , val);
				st_max[id] = max(st_max[id * 2] , st_max[id * 2 + 1]);
				st_min[id] = min(st_min[id * 2] , st_min[id * 2 + 1]);
				return;
			}
			int Get_max(int id , int l , int r , int u , int v){
				if (l > v || r < u) return 0;
				if (u <= l && r <= v) return st_max[id];
				int m = (l + r) / 2;
				pushdown(id);
				return max(Get_max(id * 2 , l , m , u , v) , Get_max(id * 2 + 1 , m + 1 , r , u , v));
			}
			int Get_min(int id , int l , int r , int u , int v){
				if (l > v || r < u) return inf;
				if (u <= l && r <= v) return st_min[id];
				int m = (l + r) / 2;
				pushdown(id);
				return min(Get_min(id * 2 , l , m , u , v) , Get_min(id * 2 + 1 , m + 1 , r , u , v));
			}
	};
	IT st;
	
	vector<int>arr[N + 2];
	
	int Find_index(vector<int>&data , int l , int bound , int nxt_bound){
		int low = l , high = sz(data) - 1 , pos = l - 1;
		while (low <= high){
			int mid = (low + high) / 2;
			if (abs(data[mid] - bound) <= abs(data[mid] - nxt_bound)){
				pos = mid;
				low = mid + 1;
			}
			else high = mid - 1;
		}
		return pos;
	}
	
	void main_code(){
		bool ok = true;
		for(int i = 1; i <= n; ++i) arr[t[i]].push_back(x[i]);
		for(int i = 1; i <= k; ++i) compress(arr[i]);
		vector<int>v;
		for(int i = 1; i <= q; ++i) v.push_back(queri[i].l);
		compress(v);
		st.load_size(sz(v));
		
//		for(auto& x : v) cout << x << ' '; cout << '\n';
		
		for(int i = 1; i <= k; ++i){
			int cur = 0;
			for(int j = 0 ; j < sz(arr[i]); ++j){
				if (j + 1 == sz(arr[i])) st.update(1 , 0 , sz(v) - 1 , cur , sz(v) - 1 , arr[i][j]);
				else {
					int nxt = Find_index(v , cur , arr[i][j] , arr[i][j + 1]);
					st.update(1 , 0 , sz(v) - 1 , cur , nxt , arr[i][j]);
//					if (i==2){
//						cout << cur << ' ' << nxt << ' ' << arr[i][j] << ' ' << arr[i][j + 1] << '\n';
//					}
					cur = nxt + 1;
				}
			}

			ok &= (sz(arr[i]) > 0);
		}
		for(int i = 1; i <= q; ++i){
//			if (i != 4) continue;
			int t = Find(v , queri[i].l) - 1;
			int x = st.Get_max(1 , 0 , sz(v) - 1 , t , t) ;
			int y = st.Get_min(1 , 0 , sz(v) - 1 , t , t) ;
//			cout << x << ' ' << y << ' ' << t << '\n';
			if (ok==false) cout<<-1<<'\n'; else 
			cout << max(abs(queri[i].l - x) , abs(queri[i].l - y)) << '\n';
		}
	}
}	

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		cin >> n >> k >> q;
		for(int i = 1; i <= n; ++i) cin >> x[i] >> t[i] >> a[i] >> b[i];
		for(int i = 1; i <= q; ++i) queri[i].read();
		if (subtask1::check()) return subtask1::main_code() , 0;
		return subtask2::main_code() , 0;
		assert(false);
	return 0;		
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:238:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:239:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20