제출 #240074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240074		alishahali1382	새 집 (APIO18_new_home)	C++14	0 / 100	5080 ms	165916 KiB

new_home

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pii, pii> pi4;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=300020, LOG=20;

vector<pair<int*, int>> todo;
struct SEGMENT{
	int seg[MAXN<<1];
	SEGMENT(){
		memset(seg, -31, sizeof(seg));
	}
	int upd(int pos, int val){
		if (seg[pos]>=val) return 0;
		todo.pb({seg+pos, seg[pos]});
		seg[pos]=val;
		return 1;
	}
	int Maximize(int l, int r, int val){
		int res=0;
		for (l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
			if (l&1) res+=upd(l++, val);
			if (r&1) res+=upd(--r, val);
		}
		return res;
	}
	int Get(int pos){
		int res=seg[0];
		for (pos+=MAXN; pos; pos>>=1) res=max(res, seg[pos]);
		return res;
	}
} seg1, seg2;

inline void undo(){
	(*todo.back().first)=todo.back().second;
	todo.pop_back();
}

int n, m, k, u, v, x, y, t, a, b, timer;
int typ[MAXN], X[MAXN], T[MAXN], A[MAXN], B[MAXN], L[MAXN], Y[MAXN];
int ans[MAXN];
vector<int> Q1[MAXN], Q2[MAXN], Q[MAXN];
vector<pi4> seg[MAXN<<2];
vector<int> compt={0, inf}, compx={0, inf+1};
multiset<int> st[MAXN];
map<pi4, int> mp;

void Add(int id, int tl, int tr, int l, int r, pi4 p){
//	if (id==1) cerr<<"event in times:"<<l<<","<<r<<" :  ["<<p.first.first<<", "<<p.first.second<<") "<<p.second.first<<' '<<p.second.second<<endl;
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		seg[id].pb(p);
		return ;
	}
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, p);
	Add(id<<1 | 1, mid, tr, l, r, p);
}

inline void f(pi4 p){
	if (!mp.count(p)) mp[p]=timer;
	else{
		Add(1, 0, MAXN, mp[p], timer, p);
		mp.erase(p);
	}
}

inline void add(multiset<int> &st, int typ, int x){
//	cerr<<"add in time "<<timer<<" : "<<typ<<", "<<x<<endl;
	if (st.count(x)){
		st.insert(x);
		return ;
	}
	st.insert(x);
	auto it=st.find(x);
	int prv=*--it, nxt=*++++it;
	f({{prv, (prv+nxt+1)/2}, {typ, 1}});
	f({{(prv+nxt+1)/2, nxt+1}, {typ, 2}});
	f({{prv, (prv+x+1)/2}, {typ, 1}});
	f({{(prv+x+1)/2, x+1}, {typ, 2}});
	f({{x, (x+nxt+1)/2}, {typ, 1}});
	f({{(x+nxt+1)/2, nxt+1}, {typ, 2}});
}

inline void rem(multiset<int> &st, int typ, int x){
//	cerr<<"rem in time "<<timer<<" : "<<typ<<", "<<x<<endl;
	st.erase(st.find(x));
	if (st.count(x)) return ;
	auto it=st.lower_bound(x);
	int nxt=*it, prv=*--it;
	f({{prv, (prv+nxt+1)/2}, {typ, 1}});
	f({{(prv+nxt+1)/2, nxt+1}, {typ, 2}});
	f({{prv, (prv+x+1)/2}, {typ, 1}});
	f({{(prv+x+1)/2, x+1}, {typ, 2}});
	f({{x, (x+nxt+1)/2}, {typ, 1}});
	f({{(x+nxt+1)/2, nxt+1}, {typ, 2}});
}

inline int gt(int x){
	return lower_bound(all(compx), x)-compx.begin();
}

void dfs(int id, int tl, int tr){
	int ted=0;
	for (pi4 p:seg[id]){
		if (p.second.second==1) ted+=seg1.Maximize(gt(p.first.first), gt(p.first.second), -p.first.first);
		if (p.second.second==2) ted+=seg2.Maximize(gt(p.first.first), gt(p.first.second), p.first.second-1);
	}
	if (tr-tl==1){
		for (int i:Q[tl]){
			ans[i]=max(ans[i], L[i]+seg1.Get(gt(L[i])));
//			debug(ans[i])
			ans[i]=max(ans[i], seg2.Get(gt(L[i]))-L[i]);
			if (ans[i]>100000000) ans[i]=-1;
		}
	}
	else{
		int mid=(tl+tr)>>1;
		dfs(id<<1, tl, mid);
		dfs(id<<1 | 1, mid, tr);
	}
	while (ted--) undo();
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k>>m;
	for (int i=1; i<=k; i++){
		st[i].insert(-inf);
		st[i].insert(inf);
		f({{0, inf+1}, {i, 2}});
		f({{-inf, 0}, {i, 1}});
	}
	for (int i=1; i<=n; i++) cin>>X[i]>>T[i]>>A[i]>>B[i], B[i]++;
	for (int i=1; i<=m; i++){
		cin>>L[i]>>Y[i];
		Y[i]=1;
		compx.pb(L[i]);
		compt.pb(Y[i]);
	}
	sort(all(compx));
	sort(all(compt));
	compx.resize(unique(all(compx))-compx.begin());
	compt.resize(unique(all(compt))-compt.begin());
//	debugv(compx)
	for (int i=1; i<=n; i++){
		A[i]=lower_bound(all(compt), A[i])-compt.begin();
		B[i]=lower_bound(all(compt), B[i])-compt.begin();
//		debug2(A[i], B[i])
		Q1[A[i]].pb(i);
		Q2[B[i]].pb(i);
	}
	for (int i=1; i<=m; i++){
		Y[i]=lower_bound(all(compt), Y[i])-compt.begin();
		Q[Y[i]].pb(i);
	}
	for (timer=0; timer<MAXN; timer++){
		for (int i:Q1[timer]) add(st[T[i]], T[i], X[i]);
		for (int i:Q2[timer]) rem(st[T[i]], T[i], X[i]);
	}
	while (mp.size()) f(mp.begin()->first);
	dfs(1, 0, MAXN);
	for (int i=1; i<=m; i++) cout<<ans[i]<<'\n';
	
	return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1


*/

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