oj.uz

Submission #212358

# Submission time Handle Problem Language Result Execution time Memory
212358 2020-03-22T18:27:11 Z mieszko11b Sweeping (JOI20_sweeping) C++14
75 / 100
 18000 ms 559304 KB 
#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;
	}
};

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, vector<ii> > M;
	set<int> on_treap;
	map<int, ii> initial_cor;
	
	Points(vector<pair<int, ii> > &P, int n) {
		this->n = n;
		T = new Treap();
		ST = new SegmentTree(inf);
		for(auto p : P) {
			M[p.Y.X].emplace_back(p.Y.Y, p.X);
			initial_cor[p.X] = p.Y;
		}
		for(auto &p : M) {
			sort(p.Y.begin(), p.Y.end(), greater<ii>());
			ST->insert(p.X, p.Y.back().X);
		}
		m = P.size();
	}
	
	~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);
		ii p;
		while((p = ST->query(0, n - s)).X <= s) {
			int x = p.Y;
			T->insert(M[x].back().Y, n - s, M[x].back().X);
			on_treap.insert(M[x].back().Y);
			M[x].pop_back();
			int v = inf;
			if(M[x].size())
				v = M[x].back().X;
			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].back().Y, x, n - s);
			on_treap.insert(M[x].back().Y);
			M[x].pop_back();
			int v = inf;
			if(M[x].size())
				v = M[x].back().X;
			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.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

sweeping.cpp: In member function 'void MasterPoints::add_point(int, int, int)':
sweeping.cpp:392:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(P.size() && P.back()->size() == PPP.size()) {
                     ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3320 KB Output is correct
2 Correct 23 ms 1024 KB Output is correct
3 Correct 25 ms 2428 KB Output is correct
4 Correct 28 ms 3072 KB Output is correct
5 Correct 43 ms 2040 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13572 ms 463768 KB Output is correct
2 Correct 13401 ms 464776 KB Output is correct
3 Correct 13429 ms 463924 KB Output is correct
4 Correct 10459 ms 474488 KB Output is correct
5 Correct 10977 ms 473244 KB Output is correct
6 Correct 13104 ms 499928 KB Output is correct
7 Correct 13282 ms 460640 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5660 ms 408860 KB Output is correct
2 Correct 5536 ms 408900 KB Output is correct
3 Correct 4752 ms 397216 KB Output is correct
4 Correct 4790 ms 403780 KB Output is correct
5 Correct 5347 ms 404672 KB Output is correct
6 Correct 5873 ms 408588 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5660 ms 408860 KB Output is correct
2 Correct 5536 ms 408900 KB Output is correct
3 Correct 4752 ms 397216 KB Output is correct
4 Correct 4790 ms 403780 KB Output is correct
5 Correct 5347 ms 404672 KB Output is correct
6 Correct 5873 ms 408588 KB Output is correct
7 Correct 7568 ms 381356 KB Output is correct
8 Correct 7325 ms 381696 KB Output is correct
9 Correct 7204 ms 381532 KB Output is correct
10 Correct 6797 ms 397080 KB Output is correct
11 Correct 7784 ms 403696 KB Output is correct
12 Correct 9135 ms 404300 KB Output is correct
13 Correct 9142 ms 404576 KB Output is correct
14 Correct 275 ms 376 KB Output is correct
15 Correct 3416 ms 100472 KB Output is correct
16 Correct 7296 ms 379856 KB Output is correct
17 Correct 6740 ms 379616 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3320 KB Output is correct
2 Correct 23 ms 1024 KB Output is correct
3 Correct 25 ms 2428 KB Output is correct
4 Correct 28 ms 3072 KB Output is correct
5 Correct 43 ms 2040 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct
7 Correct 13572 ms 463768 KB Output is correct
8 Correct 13401 ms 464776 KB Output is correct
9 Correct 13429 ms 463924 KB Output is correct
10 Correct 10459 ms 474488 KB Output is correct
11 Correct 10977 ms 473244 KB Output is correct
12 Correct 13104 ms 499928 KB Output is correct
13 Correct 13282 ms 460640 KB Output is correct
14 Correct 5660 ms 408860 KB Output is correct
15 Correct 5536 ms 408900 KB Output is correct
16 Correct 4752 ms 397216 KB Output is correct
17 Correct 4790 ms 403780 KB Output is correct
18 Correct 5347 ms 404672 KB Output is correct
19 Correct 5873 ms 408588 KB Output is correct
20 Correct 7568 ms 381356 KB Output is correct
21 Correct 7325 ms 381696 KB Output is correct
22 Correct 7204 ms 381532 KB Output is correct
23 Correct 6797 ms 397080 KB Output is correct
24 Correct 7784 ms 403696 KB Output is correct
25 Correct 9135 ms 404300 KB Output is correct
26 Correct 9142 ms 404576 KB Output is correct
27 Correct 275 ms 376 KB Output is correct
28 Correct 3416 ms 100472 KB Output is correct
29 Correct 7296 ms 379856 KB Output is correct
30 Correct 6740 ms 379616 KB Output is correct
31 Correct 9661 ms 444520 KB Output is correct
32 Correct 13921 ms 461568 KB Output is correct
33 Correct 7350 ms 402916 KB Output is correct
34 Execution timed out 18070 ms 559304 KB Time limit exceeded
35 Halted 0 ms 0 KB -