oj.uz

Submission #212355

# Submission time Handle Problem Language Result Execution time Memory
212355 2020-03-22T18:17:41 Z mieszko11b Sweeping (JOI20_sweeping) C++14
75 / 100
 18000 ms 515080 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());

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(int a, int b) {
	return uniform_int_distribution<int>(a, b)(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, sz;
	
	TreapNode(int _x, int _y) {
		x = _x;
		y = _y;
		q = rand(INT_MIN, INT_MAX);
		l = r = p = nullptr;
		lazyx = 0;
		lazyy = 0;
		sz = 1;
	}
	
	TreapNode* attach(TreapNode *ll, TreapNode *rr) {
		l = ll;
		r = rr;
		sz = 1;
		if(l != nullptr)
			l->p = this, sz += l->sz;
		if(r != nullptr)
			r->p = this, sz += r->sz;
		return this;
	}
	
	void push() {
		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 << "]";
	}
};

int szof(TreapNode *n) {
	if(n == nullptr)
		return 0;
	return n->sz;
}

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}});
		P.push_back(new Points(PPP, n));
		M[i] = P.back();
		while(P.size() > 1 && P.back()->size() == P[P.size() - 2]->size()) {
			auto P1 = P.back()->get_all_points();
			delete P.back();
			P.pop_back();
			auto P2 = P.back()->get_all_points();
			delete P.back();
			P.pop_back();
			for(auto p : P2)
				P1.push_back(p);
			P.push_back(new Points(P1, n));
			for(auto p : P1)
				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;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3320 KB Output is correct
2 Correct 31 ms 1152 KB Output is correct
3 Correct 40 ms 2552 KB Output is correct
4 Correct 37 ms 3072 KB Output is correct
5 Correct 57 ms 2168 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16525 ms 470420 KB Output is correct
2 Correct 16464 ms 471352 KB Output is correct
3 Correct 16322 ms 470632 KB Output is correct
4 Correct 12455 ms 480816 KB Output is correct
5 Correct 13740 ms 479748 KB Output is correct
6 Correct 16271 ms 506700 KB Output is correct
7 Correct 16738 ms 467280 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6416 ms 408740 KB Output is correct
2 Correct 5898 ms 409044 KB Output is correct
3 Correct 5232 ms 397248 KB Output is correct
4 Correct 5207 ms 403840 KB Output is correct
5 Correct 5545 ms 404876 KB Output is correct
6 Correct 5791 ms 408728 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6416 ms 408740 KB Output is correct
2 Correct 5898 ms 409044 KB Output is correct
3 Correct 5232 ms 397248 KB Output is correct
4 Correct 5207 ms 403840 KB Output is correct
5 Correct 5545 ms 404876 KB Output is correct
6 Correct 5791 ms 408728 KB Output is correct
7 Correct 7863 ms 381484 KB Output is correct
8 Correct 7732 ms 381576 KB Output is correct
9 Correct 7596 ms 381252 KB Output is correct
10 Correct 7067 ms 397124 KB Output is correct
11 Correct 8144 ms 403800 KB Output is correct
12 Correct 8698 ms 404328 KB Output is correct
13 Correct 8302 ms 404632 KB Output is correct
14 Correct 276 ms 256 KB Output is correct
15 Correct 3148 ms 100952 KB Output is correct
16 Correct 7648 ms 379744 KB Output is correct
17 Correct 7119 ms 379748 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3320 KB Output is correct
2 Correct 31 ms 1152 KB Output is correct
3 Correct 40 ms 2552 KB Output is correct
4 Correct 37 ms 3072 KB Output is correct
5 Correct 57 ms 2168 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 16525 ms 470420 KB Output is correct
8 Correct 16464 ms 471352 KB Output is correct
9 Correct 16322 ms 470632 KB Output is correct
10 Correct 12455 ms 480816 KB Output is correct
11 Correct 13740 ms 479748 KB Output is correct
12 Correct 16271 ms 506700 KB Output is correct
13 Correct 16738 ms 467280 KB Output is correct
14 Correct 6416 ms 408740 KB Output is correct
15 Correct 5898 ms 409044 KB Output is correct
16 Correct 5232 ms 397248 KB Output is correct
17 Correct 5207 ms 403840 KB Output is correct
18 Correct 5545 ms 404876 KB Output is correct
19 Correct 5791 ms 408728 KB Output is correct
20 Correct 7863 ms 381484 KB Output is correct
21 Correct 7732 ms 381576 KB Output is correct
22 Correct 7596 ms 381252 KB Output is correct
23 Correct 7067 ms 397124 KB Output is correct
24 Correct 8144 ms 403800 KB Output is correct
25 Correct 8698 ms 404328 KB Output is correct
26 Correct 8302 ms 404632 KB Output is correct
27 Correct 276 ms 256 KB Output is correct
28 Correct 3148 ms 100952 KB Output is correct
29 Correct 7648 ms 379744 KB Output is correct
30 Correct 7119 ms 379748 KB Output is correct
31 Correct 12023 ms 451548 KB Output is correct
32 Correct 16710 ms 468388 KB Output is correct
33 Correct 9152 ms 410112 KB Output is correct
34 Execution timed out 18117 ms 515080 KB Time limit exceeded
35 Halted 0 ms 0 KB -