Submission #587375

#	Time	Username	Problem	Language	Result	Execution time	Memory
587375		AlperenT	Robots (IOI13_robots)	C++17	0 / 100	36 ms	65536 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

const int N = 1e6 + 5e4 + 5;

int ans = 0;

map<int, int> cmprsx, cmprsy;
multiset<int> curx, cury, curw, curs;
vector<int> used;

struct SegTree{
	pair<int, int> tree[N * 4];
	multiset<int> st[N * 4];

	SegTree(){
		for(int i = 0; i < N * 4; i++) st[i].insert(0);
	}

	void update(int pos, int val, int v = 1, int l = 1, int r = N - 1){
		if(l == r) st[v].insert(val), tree[v] = {*prev(st[v].end()), l};
		else{
			int m = l + (r - l) / 2;

			if(pos <= m) update(pos, val, v * 2, l, m);
			else update(pos, val, v * 2 + 1, m + 1, r);

			tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
		}
	}

	void update2(int pos, int val, int v = 1, int l = 1, int r = N - 1){
		if(l == r){
			st[v].erase(st[v].find(val));
			tree[v] = {*prev(st[v].end()), l};
		}
		else{
			int m = l + (r - l) / 2;

			if(pos <= m) update2(pos, val, v * 2, l, m);
			else update2(pos, val, v * 2 + 1, m + 1, r);

			tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
		}
	}

	pair<int, int> query(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
		if(l > r) return {0, 0};
		else if(l == tl && r == tr) return tree[v];
		else{
			int tm = tl + (tr - tl) / 2;

			return max(query(l, min(tm, r), v * 2, tl, tm), query(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
		}
	}
};

SegTree wsgt, ssgt;

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]){
	for(int i = 0; i < a; i++) cmprsx[x[i]] = 1;
	for(int i = 0; i < b; i++) cmprsy[y[i]] = 1;

	for(int i = 0; i < t; i++) cmprsx[w[i]] = cmprsy[s[i]] = 1;

	int tmp = 0;

	for(auto &p : cmprsx) p.second = ++tmp;

	tmp = 0;

	for(auto &p : cmprsy) p.second = ++tmp;

	for(int i = 0; i < a; i++) x[i] = cmprsx[x[i]];
	for(int i = 0; i < b; i++) y[i] = cmprsy[y[i]];

	for(int i = 0; i < t; i++) w[i] = cmprsx[w[i]], s[i] = cmprsy[s[i]];

	sort(x, x + a);
	sort(y, y + b);

	for(int i = 0; i < a; i++) curx.insert(x[i]);
	for(int i = 0; i < b; i++) cury.insert(y[i]);
	for(int i = 0; i < t; i++) curw.insert(w[i]), curs.insert(s[i]);

	for(int i = 0; i < t; i++) wsgt.update(w[i], s[i]), ssgt.update(s[i], w[i]);

	while(curw.size()){
		bool flag = false;
		ans++;

		used.clear();

		while(!curw.empty() && !curx.empty()){
			int ww = *curw.begin();

			auto it = curx.upper_bound(ww);

			if(it == curx.end()) break;

			int xx = *it;

			curx.erase(it);

			used.push_back(xx);

			pair<int, int> p = wsgt.query(1, xx - 1);

			curw.erase(curw.find(p.second));
			curs.erase(curs.find(p.first));

			wsgt.update2(p.second, p.first);
			ssgt.update2(p.first, p.second);

			flag = true;
		}

		for(auto xx : used) curx.insert(xx);

		used.clear();

		while(!curs.empty() && !cury.empty()){
			int ss = *curs.begin();

			auto it = cury.upper_bound(ss);

			if(it == cury.end()) break;

			int yy = *it;

			cury.erase(it);

			used.push_back(yy);

			pair<int, int> p = ssgt.query(1, yy - 1);

			curs.erase(curs.find(p.second));
			curw.erase(curw.find(p.first));

			ssgt.update2(p.second, p.first);
			wsgt.update2(p.first, p.second);

			flag = true;
		}

		for(auto yy : used) cury.insert(yy);

		if(flag == false) return -1;
	}

    return ans;
}

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