Submission #346515

#	Time	Username	Problem	Language	Result	Execution time	Memory
346515		wwdd	Robots (IOI13_robots)	C++14	100 / 100	2453 ms	21588 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int,int> ii;
class ST {
	private:
		int n,h;
		vl st,lz;
		const ll STV = -1LL<<62;
		int log2(int v) {
			if(v <= 1) {return 1;}
			return log2(v/2)+1;
		}
		void ap(int p, ll val) {
			st[p] += val;
			if(p < n) {lz[p] += val;}
		}
		void build(int p) {
			while(p > 1) {
				p >>= 1;
				if(p >= n) {continue;}
				st[p] = max(st[p<<1],st[p<<1|1])+lz[p];
			}
		}
		void psh(int p) {
			for(int s=h;s>0;s--) {
				int i = p>>s;
				if(lz[i] != 0) {
					ap(i<<1,lz[i]);
					ap(i<<1|1,lz[i]);
					lz[i] = 0;
				}
			}
		}
	public:
		ST(int n_) {
			n = n_;
			st.assign(2*n,0);
			lz.assign(n,0);
		}
		void reset(ll cons) {
			lz.assign(n,0);
			for(int i=0;i<n;i++) {
				st[i+n] = -cons*i;
			}
			for(int i=n-1;i>0;i--) {
				st[i] = max(st[i<<1],st[i<<1|1]);
			}
		}
		void up(int l, int r, ll val) {
			if(l >= r) {return;}
			l += n;r += n;
			int li = l,ri = r;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {ap(l,val);l++;}
				if(r&1) {--r;ap(r,val);}
			}
			build(li);build(ri-1);
		}
		ll get(int l, int r) {
			l += n;r += n;
			psh(l);psh(r-1);
			ll res = STV;
			for(;l<r;l>>=1,r>>=1) {
				if(l&1) {res = max(res,st[l]);l++;}
				if(r&1) {--r;res = max(res,st[r]);}
			}
			return res;
		}
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	vector<ii> wa;
	for(int i=0;i<T;i++) {
		wa.emplace_back(W[i],S[i]);
	}
	sort(X,X+A);
	sort(Y,Y+B);
	sort(wa.begin(),wa.end());
	for(int i=T-1;i>=0;i--) {
		int wol = upper_bound(X,X+A,wa[i].first)-X;
		int sol = upper_bound(Y,Y+B,wa[i].second)-Y;
		wa[i] = {wol,sol};
	}
	ST su(B+1);
	int st = 1,ed = T;
	int ls = -1;
	while(st <= ed) {
		int m = (st+ed)/2;
		bool poss = true;
		su.reset(m);
		int bt = A;
		for(int i=T-1;i>=0;i--) {
			if(!poss) {break;}
			while(bt > wa[i].first) {
				if(su.get(0,B+1) > 0) {
					poss = false;break;
				}
				su.up(0,B+1,-m);
				bt--;
			}
			if(!poss) {break;}
			int bu = B-wa[i].second;
			su.up(bu,B+1,1);
		}
		if(su.get(0,B+1) > 0) {
			poss = false;
		}
		if(poss) {
			ls = m;
			ed = m-1;
		} else {
			st = m+1;
		}
	}
	return ls;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10