Submission #217530

#	Time	Username	Problem	Language	Result	Execution time	Memory
217530		mieszko11b	Sweeping (JOI20_sweeping)	C++14	100 / 100	12479 ms	257072 KiB

sweeping

#include <bits/stdc++.h>
 
using namespace std;
 
using ii = pair<int, int>;
 
const int inf = 1e9 + 7;
 
#define X first
#define Y second
 
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
 
uniform_int_distribution<int> uid(INT_MIN, INT_MAX);
 
void readint(int &a) {
	char c;
	a = 0;
	do {
		c = getchar_unlocked();
	} while(c < '0' || c > '9');
	do {
		a = a * 10 + c - '0';
		c = getchar_unlocked();
	} while(c >= '0' && c <= '9');
}
 
int rand() {
	return uid(rng);
}
 
struct SegmentTree {
	int lv;
	vector<pair<int, int> > d;
	vector<int> x;
	vector<int> ind;
	
	SegmentTree(vector<pair<int, ii>> V) {
		int n = V.size();
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
		d.resize(2 * lv + 2, {inf, inf});
		x.resize(lv + 2, inf);
		ind.resize(lv + 2, inf);
		
		for(int i = 0 ; i < V.size() ; i++) {
			d[lv + i] = {V[i].Y.Y, i};
			x[i] = V[i].Y.X;
			ind[i] = V[i].X;
		}
			
		for(int i = lv - 1 ; i >= 1 ; i--)
			d[i] = min(d[2 * i], d[2 * i + 1]);
	}
	
	// ind, {x, y}
	ii _query(int a, int b) {
		if(b < a)
			return {inf, inf};
		
		int va = lv + a;
		int vb = lv + b;
		auto res = min(d[va], d[vb]);
		
		while(va / 2 != vb / 2) {
			if(va % 2 == 0)
				res = min(res, d[va + 1]);
			if(vb % 2 == 1)
				res = min(res, d[vb - 1]);
			va /= 2;
			vb /= 2;
		}
		
		return res;
	}
	
	void insert(int w, int v) {
		w += lv;
		d[w].X = v;
		w /= 2;
		while(w) {
			d[w] = min(d[2 * w], d[2 * w + 1]);
			w /= 2;
		}
	}
	
	// x <= l
	pair<int, ii> query(int l, int y) {
		auto it = upper_bound(x.begin(), x.end(), l);
		int a = 0;
		int b = distance(x.begin(), it) - 1;
		ii p = _query(a, b);
		if(p.X > y)
			return {-1, {-1, -1}};
			
		insert(p.Y, inf);
		return {ind[p.Y], {x[p.Y], p.X}};
	}
};
 
struct TreapNode {
	TreapNode *l, *r, *p;
	int x, y, q, lazyx, lazyy;
	
	TreapNode(int _x, int _y) {
		x = _x;
		y = _y;
		q = rand();
		l = r = p = nullptr;
		lazyx = 0;
		lazyy = 0;
	}
	
	TreapNode* attach(TreapNode *ll, TreapNode *rr) {
		l = ll;
		r = rr;
		if(l != nullptr)
			l->p = this;
		if(r != nullptr)
			r->p = this;
		return this;
	}
	
	void push() {
		if(!lazyx && !lazyy)
			return ;
		
		x = max(x, lazyx);
		y = max(y, lazyy);
		if(l != nullptr) {
			l->lazyx = max(l->lazyx, lazyx);
			l->lazyy = max(l->lazyy, lazyy);
		}
		
		if(r != nullptr) {
			r->lazyx = max(r->lazyx, lazyx);
			r->lazyy = max(r->lazyy, lazyy);
		}
		
		lazyx = 0;
		lazyy = 0;
	}
	
	void print() {
		push();
		cout << "[";
		if(l != nullptr)
			l->print();
		cout << "]";
		cout << "(" << x << ", " << y << ")[";
		if(r != nullptr)
			r->print();
		cout << "]";
	}
};
 
struct Treap {
	TreapNode *root;
	map<int, TreapNode*> M;
	int total;
	
	Treap() {
		root = new TreapNode(0, 0);
		total = 1;
	}
	
	~Treap() {
		for(auto p : M)
			delete p.Y;
	}
	
	TreapNode* merge(TreapNode *a, TreapNode *b) {
		if(a == nullptr)
			return b;
		if(b == nullptr)
			return a;
			
		a->push();
		b->push();
			
		if(a->q < b->q)
			return a->attach(a->l, merge(a->r, b));
		else
			return b->attach(merge(a, b->l), b->r);
	}
	
	bool comp(int x1, int y1, int x2, int y2) {
		return (x1 < x2 || y1 > y2);
	}
	
	pair<TreapNode*, TreapNode*> split(TreapNode *n, int x, int y) {
		if(n == nullptr)
			return {nullptr, nullptr};
		n->push();
		if(comp(x, y, n->x, n->y)) {
			TreapNode *m = n->l;
			n->attach(nullptr, n->r);
			auto p = split(m, x, y);
			return {p.X, n->attach(p.Y, n->r)};
		} else {
			TreapNode *m = n->r;
			n->attach(n->l, nullptr);
			auto p = split(m, x, y);
			return {n->attach(n->l, p.X), p.Y};
		}
	}
	
	void insert(int i, int x, int y) {
		TreapNode *n = new TreapNode(x, y);
		M[i] = n;
		auto p = split(root, x, y);
		root = merge(merge(p.X, n), p.Y);
		total++;
	}
	
	// dla x' <= x
	void maxy(int x, int v) {
		auto p = split(root, x, -1);
		if(p.X != nullptr)
			p.X->lazyy = max(p.X->lazyy, v);
		root = merge(p.X, p.Y);
	}
	
	// dla y' <= y
	void maxx(int y, int v) {
		auto p = split(root, inf, y+1);
		//~ cout << "maxx split" << endl;
		//~ if(p.X != nullptr) p.X->print(); cout << endl;
		//~ if(p.Y != nullptr) p.Y->print(); cout << endl;
		if(p.Y != nullptr)
			p.Y->lazyx = max(p.Y->lazyx, v);
		root = merge(p.X, p.Y);
	}
	
	void process_lazy_up(TreapNode *n) {
		if(n == nullptr)
			return ;
		process_lazy_up(n->p);
		n->push();
	}
	
	ii query(int i) {
		TreapNode *n = M[i];
		process_lazy_up(n);
		return {n->x, n->y};
	}
	
	void print() {
		root->print();
		cerr << endl;
	}
	
	void push(TreapNode *n) {
		if(n == nullptr)
			return ;
		n->push();
		push(n->l);
		push(n->r);
	}
	
	vector<pair<int, ii> > pushall() {
		push(root);
		vector<pair<int, ii> > res;
		res.reserve(total);
		for(auto p : M)
			res.push_back({p.X, {p.Y->x, p.Y->y}});
		return res;
	}
};
 
struct Points {
	// inicjalizujemy punktami, ktore sie nie zmieniaja
	// wrzucamy wszystkie na drzewo i mape wektorow
	// treap pusty
	// przy kazdym zapytaniu najpierw aktualizujemy treapa, potem przerzucamy na niego punkty
	
	int n, m;
	Treap *T;
	SegmentTree *ST;
	set<int> on_treap;
	map<int, ii> initial_cor;
	
	static bool compp(const pair<int, ii> &a, const pair<int, ii> &b) {
		return a.Y.X < b.Y.X;
	}
	
	Points(vector<pair<int, ii> > &P, int n) {
		this->n = n;
		T = new Treap();

		m = P.size();
		sort(P.begin(), P.end(), compp);
		ST = new SegmentTree(P);
		for(auto p : P)
			initial_cor[p.X] = p.Y;
	}
	
	~Points() {
		delete T;
		delete ST;
	}
	
	ii query(int i) {
		if(on_treap.count(i))
			return T->query(i);
		else
			return initial_cor[i];
	}
	
	void sweep_horizontally(int s) {
		T->maxx(s, n - s);
		pair<int, ii> p;
		while((p = ST->query(n - s, s)).X != -1) {
			T->insert(p.X, n - s, p.Y.Y);
			on_treap.insert(p.X);
		}
	}
	
	void sweep_vertically(int s) {
		T->maxy(s, n - s);
		pair<int, ii> p;
		while((p = ST->query(s, n - s)).X != -1) {
			T->insert(p.X, p.Y.X, n - s);
			on_treap.insert(p.X);
		}
	}
	
	int size() {
		return m;
	}
	
	vector<pair<int, ii> > get_all_points() {
		vector<pair<int, ii>> res = T->pushall();
		for(auto p : initial_cor) {
			if(!on_treap.count(p.X))
				res.push_back({p.X, p.Y});
		}
		return res;
	}
};
 
struct MasterPoints {
	int n;
	Points *I;
	vector<Points*> P;
	map<int, Points*> M;
	
	MasterPoints(vector<pair<int, ii> > &P, int n) {
		this->n = n;
		I = new Points(P, n);
		for(auto p : P)
			M[p.X] = I;
	}
	
	ii query(int i) {
		return M[i]->query(i);
	}
	
	void sweep_horizontally(int s) {
		I->sweep_horizontally(s);
		for(auto p : P)
			p->sweep_horizontally(s);
	}
	
	void sweep_vertically(int s) {
		I->sweep_vertically(s);
		for(auto p : P)
			p->sweep_vertically(s);
	}
	
	void add_point(int i, int x, int y) {
		vector<pair<int, ii> > PPP;
		PPP.push_back({i, {x, y}});
		while(P.size() && P.back()->size() == PPP.size()) {
			auto P1 = P.back()->get_all_points();
			delete P.back();
			P.pop_back();
			for(auto p : P1)
				PPP.push_back(p);
		}
		
		P.push_back(new Points(PPP, n));
		for(auto p : PPP)
			M[p.X] = P.back();
		//~ cerr << P.size() << endl;
	}
};
 
int n, m, q;
MasterPoints *PP;
 
int main() {
	//~ scanf("%d%d%d", &n, &m, &q);
	readint(n);
	readint(m);
	readint(q);
 
	vector<pair<int, ii> > P;
	for(int i = 1 ; i <= m ; i++) {
		int a, b;
		//~ scanf("%d%d", &a, &b);
		readint(a);
		readint(b);
		P.push_back({i, {a, b}});
	}
	
	PP = new MasterPoints(P, n);
 
	int cnt = m;
	while(q--) {
		//~ cout << q << endl;
		int t;
		//~ scanf("%d", &t);
		readint(t);
		if(t == 1) {
			int i;
			//~ scanf("%d", &i);
			readint(i);
			ii p = PP->query(i);
			printf("%d %d\n", p.X, p.Y);
		} else if(t == 2) {
			int s;
			//~ scanf("%d", &s);
			readint(s);
			PP->sweep_horizontally(s);
		} else if(t == 3) {
			int s;
			//~ scanf("%d", &s);
			readint(s);
			PP->sweep_vertically(s);
		} else {
			int a, b;
			//~ scanf("%d%d", &a, &b);
			readint(a);
			readint(b);
			PP->add_point(++cnt, a, b);
		}
		
		//~ cout << "TREAP\n";
		//~ PP->T->print();
	}
 
	return 0;
}

Compilation message (stderr)

sweeping.cpp: In constructor 'SegmentTree::SegmentTree(std::vector<std::pair<int, std::pair<int, int> > >)':
sweeping.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < V.size() ; i++) {
                   ~~^~~~~~~~~~
sweeping.cpp: In member function 'void MasterPoints::add_point(int, int, int)':
sweeping.cpp:375:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(P.size() && P.back()->size() == PPP.size()) {
                     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25