Submission #212364

#	Time	Username	Problem	Language	Result	Execution time	Memory
212364		mieszko11b	Sweeping (JOI20_sweeping)	C++14	75 / 100	18115 ms	493444 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 STNode {
	STNode *l, *r;
	ii v;
	
	STNode(ii v = {inf, inf}) {
		this->v = v;
		l = r = nullptr;
	}
	
	void upd() {
		v = {inf, inf};
		if(l != nullptr)
			v = min(v, l->v);
		if(r != nullptr)
			v = min(v, r->v);
	}
};

struct SegmentTree {
	int lv;
	STNode *root;
	
	SegmentTree(int n) {
		root = new STNode();
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
	}
	
	void del_nodes(STNode *n) {
		if(n == nullptr)
			return ;
		del_nodes(n->l);
		del_nodes(n->r);
		delete n;
	}
	
	~SegmentTree() {
		del_nodes(root);
	}
	
	void insert(STNode *&n, int l, int r, int w, int v) {
		//~ cout << "a" << endl;
		if(n == nullptr)
			n = new STNode();
		if(l == r) {
			n->v = {v, l};
			return ;
		}
		if(w <= (l + r) / 2)
			insert(n->l, l, (l + r) / 2, w, v);
		else
			insert(n->r, (l + r) / 2 + 1, r, w, v);
		n->upd();
	}
	
	ii query(STNode *&n, int l, int r, int a, int b) {
		if(n == nullptr || r < a || l > b || l > r)
			return {inf, inf};
		if(a <= l && r <= b)
			return n->v;
		return min(query(n->l, l, (l + r) / 2, a, b),
			query(n->r, (l + r) / 2 + 1, r, a, b));
	}
	
	void insert(int w, int v) {
		insert(root, 0, lv - 1, w, v);
	}
	
	ii query(int a, int b) {
		return query(root, 0, lv - 1, a, b);
	}
};

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;
	}
};

bool on_treap[2000007];
int nxt[2000007];

bool comp(pair<int, ii> &a, pair<int, ii> &b) {
	return a.Y < b.Y;
}

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;
	map<int, ii> initial_cor;
	map<int, int> M;
	
	Points(vector<pair<int, ii> > &P, int n) {
		this->n = n;
		T = new Treap();
		ST = new SegmentTree(inf);
		sort(P.begin(), P.end(), comp);
		for(int i = 0 ; i < P.size() ; i++) {
			initial_cor[P[i].X] = P[i].Y;
			if(i + 1 < P.size() && P[i + 1].Y.X == P[i].Y.X)
				nxt[P[i].X] = P[i + 1].X;
			else
				nxt[P[i].X] = -1;
			if(i == 0 || P[i - 1].Y.X < P[i].Y.X) {
				ST->insert(P[i].Y.X, P[i].Y.Y);
				M[P[i].Y.X] = P[i].X;
			}
		}
		m = P.size();
	}
	
	~Points() {
		for(auto p : initial_cor)
			on_treap[p.X] = 0;
		delete T;
		delete ST;
	}
	
	ii query(int i) {
		if(on_treap[i])
			return T->query(i);
		else
			return initial_cor[i];
	}
	
	void sweep_horizontally(int s) {
		T->maxx(s, n - s);
		ii p;
		while((p = ST->query(0, n - s)).X <= s) {
			int x = p.Y;
			T->insert(M[x], n - s, initial_cor[M[x]].Y);
			on_treap[M[x]] = 1;
			M[x] = nxt[M[x]];
			int v = inf;
			if(M[x] != -1)
				v = initial_cor[M[x]].Y;
			ST->insert(x, v);
		}
	}
	
	void sweep_vertically(int s) {
		T->maxy(s, n - s);
		ii p;
		while((p = ST->query(0, s)).X <= n - s) {
			int x = p.Y;
			T->insert(M[x], x, n - s);
			on_treap[M[x]] = 1;
			M[x] = nxt[M[x]];
			int v = inf;
			if(M[x] != -1)
				v = initial_cor[M[x]].Y;
			ST->insert(x, v);
		}
	}
	
	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[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 'Points::Points(std::vector<std::pair<int, std::pair<int, int> > >&, int)':
sweeping.cpp:300:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < P.size() ; i++) {
                   ~~^~~~~~~~~~
sweeping.cpp:302:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i + 1 < P.size() && P[i + 1].Y.X == P[i].Y.X)
       ~~~~~~^~~~~~~~~~
sweeping.cpp: In member function 'void MasterPoints::add_point(int, int, int)':
sweeping.cpp:404: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: 0 / 25