Submission #1261889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261889		_rain_	New Home (APIO18_new_home)	C++20	0 / 100	109 ms	70972 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;
	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 n <= 400 && q <= 400;
	}
	
	int cnt[N + 2] = {};
		void reset_type(){
			for(int i = 1; i <= k; ++i) cnt[i] = 0;
			return;
		}
	
	void main_code(){
		for(int i = 1; i <= q; ++i){
			int l = queri[i].l , y = queri[i].y;
			reset_type();
			int ans = 0;
			for(int j = 1; j <= n; ++j) {
				if (y > b[j] || y < a[j]) continue;
				cnt[t[j]]++;
				maximize(ans , abs(x[j] - l));
			}
			bool ok = true;
			for(int j = 1; j <= k; ++j) ok &= (cnt[j] > 0);
			if (ok==false) cout << -1 << '\n'; else cout << ans << '\n';
		}
	}
}

namespace subtask2{
	bool check(){
		return true;
	}
	
	const int MAXN = (int) N * 3;
		vector<int>nen;
		vector<pair<int,int>>open[MAXN + 2] , close[MAXN + 2] , ask[MAXN + 2];
		
	multiset<pair<int,int>>st;
	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});
		}
		
		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.insert(x);
			}
			for(auto x : ask[i]){
				if (full != k) ans[x.second] = -1;
				else {
					assert(st.size());
					pair<int,int> t1 = *st.begin();
					pair<int,int> t2 = *st.rbegin();
					ans[x.second] = max(abs(x.first - t1.first) , abs(x.first - t2.first));
				}
			}
			for(auto x : close[i]) {
				//... setalize
					full -= (cnt[x.second] > 0);
					cnt[x.second]--;
					full += (cnt[x.second] > 0);
					
				st.erase(st.find(x));
			}
		}
		for(int i = 1; i <= q; ++i) cout << ans[i] << '\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".ans","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:135:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:136:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |                         freopen(name".ans","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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