Submission #109088

#	Time	Username	Problem	Language	Result	Execution time	Memory
109088		ryansee	New Home (APIO18_new_home)	C++14	57 / 100	5049 ms	167396 KiB

new_home

#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll /*long long*/ int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n,k,q,ans[MAXN]; vector<ll>d;
struct store {
	int l, type, a, b, i;
} A[MAXN];
vector<store>types[MAXN];
spi Q[MAXN]; // location, time(a,b) with respects to above
struct rays {
	int x=0, in=0, a=0, b=0; // x - point, influence, [a,b] (means inclusive)
	void close(ll y) { assert(b==-1); b = y; }
}; vector<rays>neg,pos;
set <pi> ms;
int currind_pos[MAXN], currind_neg[MAXN];
struct node {
	int s,e,m;
	ll v, lv;
	node *l, *r;
	node(ll _S, ll _E) {
		s = _S, e = _E, m = (s+e)/2;
		v = -INF; lv = -INF;
		if(s!=e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	void update(ll x, ll y, ll nv) {
		if(x>y)return;
		if(s==x&&e==y) { v = max(v, nv); return; }
		if(x>m) r->update(x,y,nv);
		else if(y<=m) l->update(x,y,nv);
		else l->update(x,m,nv), r->update(m+1,y,nv);
      	lv = max({l->lv, r->lv,l->v,r->v});
	}
	ll rmq(ll x) {
		if(s==e||v>lv) return v;
		if(x>m) return max(v,r->rmq(x));
		else return max(v,l->rmq(x));
		assert(0);
	}
	void reset() {
	    v = -INF;
	    if(s==e) return;
	    l->reset();
	    r->reset();
	}
} *seg;
ll idx(ll x) { return lbd(d,x)-d.begin(); }
void solve() { 
	FOR(i,0,n) types[A[i].type].pb(A[i]);
	FOR(K,1,k+1) {
		if(types[K].empty()) continue;
// 		sort(all(types[K]), [] (store x, store y) { return x.l < y.l; } ); 
		vector<spi>events; // year to carry out, open/close, index
		for(auto i : types[K]) events.pb(spi(i.a,pi(0,i.i))), events.pb(spi(i.b,pi(1,i.i)));
		sort(all(events)); ms.clear();
		// insert dummy for neg, as well as ms
		ms.ins(pi(-INF,n)); 
		ms.ins(pi(INF,n+1));
		for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
		for(auto i : events) {
			ll year = i.f, ind = i.s.s;
			bool op = i.s.f; ll x = A[ind].l;
			if(op == 0) { // open 
				ms.ins(pi(x,ind));
				auto itr = ms.find(pi(x,ind));
				auto itr2 = next(itr);
				--itr;
				// itr -> prev x, itr2 -> next x
				
				/* neg rays */
				// close ray from next to prev, set end time to (year - 1);
				// open ray from curr to prev, set start time to (year);
				// open ray from next to curr, set start time to (year);
				ll ci = currind_neg[itr2->s]; 
				if(ci == -1) { }
				else neg[ci].close(year-1); // close ray from next to prev, set end time to (year - 1);
				
				currind_neg[ind] = (int)neg.size(); // open ray from curr to prev, set start time to (year);
				neg.pb({x,x-(x-itr->f)/2,year,-1});
				// cerr << ind << ' ' << currind[ind] << '\n';
				if(itr2->s < n) {
					currind_neg[itr2->s] = (int)neg.size(); 	// open ray from next to curr, set start time to (year);
					neg.pb({itr2->f, itr2->f-(itr2->f-x)/2,year,-1});
				}
				/* */
				/* pos rays */
				// close ray from prev to next, set end time to (year-1);
				// open ray from prev to curr, set start time to (year);
				// open ray from curr to next, set start time to (year);
				ci = currind_pos[itr->s];
				if(ci == -1) { }
				else pos[ci].close(year-1); // close ray from prev to next, set end time to (year-1);
				
				if(itr->s < n) {
					currind_pos[itr->s] = (int)pos.size();
					pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year);
				}
				
				currind_pos[ind] = (int)pos.size();
				pos.pb({x,x+(itr2->f-x)/2,year,-1}); // open ray from curr to next, set start time to (year);
				/* */
			} else {
				auto itr2 = ms.erase(ms.find(pi(x,ind)));
				auto itr = prev(itr2);
				/* neg rays */
				// close ray from curr to prev, end time: year
				// close ray from next to curr, end time: year
				// open ray from next to prev, start time: year+1
				ll ci = currind_neg[ind];
				neg[ci].close(year); // close ray from curr to prev, end time: year
				ci = currind_neg[itr2->s]; if(0)cerr << ci << ' ' << neg.size() << ' ' << itr2->s << '\n';
				if(ci == -1) {} 
				else neg[ci].close(year); // close ray from next to curr, end time: year
				
				if(itr2->s < n) {
					currind_neg[itr2->s] = (int)neg.size();
					neg.pb({itr2->f, itr2->f-(itr2->f-itr->f)/2,year+1,-1}); // open ray from next to prev, start time: year+1
				}
				/* */
				
				/* pos rays */
				// close ray from prev to curr, end time: year
				// close ray from curr to next, end time: year
				// open ray from prev to next, start time: year+1
				ci = currind_pos[itr->s];
				if(ci == -1) { }
				else pos[ci].close(year); // close ray from prev to curr, end time: year
				
				ci = currind_pos[ind];
				assert(ci!=-1);
				pos[ci].close(year); // close ray from curr to next, end time: year
				
				if(itr->s < n) {
					currind_pos[itr->s] = (int)pos.size();
					pos.pb({itr->f,itr->f+(itr2->f-itr->f)/2,year+1,-1}); // open ray from prev to next, start time: year+1
				}
				/* */
			}
		}
		for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
	}
	for(auto &i : neg) if(i.b == -1) i.b = INF;
	for(auto &i : pos) if(i.b == -1) i.b = INF;
	// for(auto &i : neg) cerr << i.x << ' ' << i.in << ' ' << i.a << ' ' << i.b << '\n';
	// for(auto &i : pos) cerr << i.x << ' ' << i.in << ' ' << i.a << ' ' << i.b << '\n';
	if(0) { FOR(i,0,n) d.pb(A[i].a), d.pb(A[i].b); } for(auto i : neg) d.pb(i.a),d.pb(i.b); for(auto i : pos) d.pb(i.a), d.pb(i.b);
	d.pb(-INF); d.pb(INF);
	sort(all(d)); d.resize(unique(all(d))-d.begin());
	seg=new node(0,siz(d)-1);
	sort(Q,Q+q);
	sort(all(neg), [] (rays x, rays y) { return x.in < y.in; });
	ll co = 0;
	FOR(i,0,q) {
		ll l = Q[i].f, t = Q[i].s.f; ll ind = Q[i].s.s;
		while(co < neg.size() && neg[co].in <= l) {
			seg->update(idx(neg[co].a), idx(neg[co].b), neg[co].x);
			++co;
		}
		ans[ind]=seg->rmq(idx(t))-l;
	}
	if(0) seg=new node(0,siz(d)-1); seg->reset();
	co = 0;
	sort(all(pos), [] (rays x, rays y) { return x.in > y.in; });
// 	reverse(Q,Q+q);
	for(ll i=q-1;i>=0;--i) {
		ll l = Q[i].f, t = Q[i].s.f, ind = Q[i].s.s;
		while(co < pos.size() && pos[co].in >= l) {
			seg->update(idx(pos[co].a), idx(pos[co].b), -pos[co].x);
			++co;
		}
		ans[ind]=max(ans[ind],seg->rmq(idx(t))+l);
	}
	return;
}
/* for when u need negative numbers too */
inline int ri() {
	bool neg = false;
	int res = 0;
	char c = getchar_unlocked();
	while (true) {
		if (c=='-') break;
		if ('0'<=c && c<='9') break;
		c = getchar_unlocked();
	}
	if (c=='-') neg = true;
	else res = c-'0';
	while (true) {
		c = getchar_unlocked();
		if (c<'0' || c>'9') break;
		res = (res<<1) + (res<<3) + (c-'0');
	}
	if (neg) return -res;
	return res;
}
int main()
{
	FAST
	//cin>>n>>k>>q;
  n=ri(),k=ri(),q=ri();
	FOR(i,0,n) { A[i].l=ri(),A[i].type=ri(),A[i].a=ri(),A[i].b=ri();if(0)cin>>A[i].l>>A[i].type>>A[i].a>>A[i].b; A[i].i = i; }
	FOR(i,0,q) {Q[i].f=ri(),Q[i].s.f=ri();if(0)cin>>Q[i].f>>Q[i].s.f;Q[i].s.s=i;}
	
// 	FOR(i,0,n) d.pb(A[i].a), d.pb(A[i].b);
	FOR(i,0,q) d.pb(Q[i].s.f);
// 	sort(all(d)); d.resize(unique(all(d))-d.begin());
	solve(); // get_neg_rays, & pos_rays;
	// check for -1 case here i guess:
	#define storeco currind_pos
	mmst(storeco,0);
	sort(Q,Q+q,[](spi x, spi y){return x.s.f < y.s.f; });
	sort(A,A+n,[](store x, store y){return x.a<y.a;});
	ll co = 0; multiset <pi> ms; multiset <int> deci; FOR(i,1,k+1) deci.ins(0);
	FOR(i,0,q) {
		ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s;
		while(co < n && A[co].a <= t) {
			ms.ins(pi(A[co].b, A[co].type));
			deci.erase(deci.find(storeco[A[co].type]));
			storeco[A[co].type] ++;
			deci.ins(storeco[A[co].type]);
			++co;
		}
		while(ms.size() && ms.begin()->f < t) {
			deci.erase(deci.find(storeco[ms.begin()->s]));
			storeco[ms.begin()->s] --;
			deci.ins(storeco[ms.begin()->s]);
			ms.erase(ms.begin());
		}
		if(*deci.begin() == 0) ans[ind] = -1;
	}
	FOR(i,0,q) cout << ans[i] << '\n';
}
/*
 * 
2 1 1
5 1 1 5
4 1 1 4
5 3
*/

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:91:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
   ^~~
new_home.cpp:91:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
                                                                  ^~~~~~~~~~~
new_home.cpp:172:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
   ^~~
new_home.cpp:172:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
                                                                 ^~~~~~~~~~~
new_home.cpp:187:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(co < neg.size() && neg[co].in <= l) {
         ~~~^~~~~~~~~~~~
new_home.cpp:193:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(0) seg=new node(0,siz(d)-1); seg->reset();
  ^~
new_home.cpp:193:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(0) seg=new node(0,siz(d)-1); seg->reset();
                                  ^~~
new_home.cpp:199:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(co < pos.size() && pos[co].in >= l) {
         ~~~^~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:246:6: warning: unused variable 'l' [-Wunused-variable]
   ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s;
      ^

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