oj.uz

Submission #212345

# Submission time Handle Problem Language Result Execution time Memory
212345 2020-03-22T17:56:34 Z mieszko11b Sweeping (JOI20_sweeping) C++14
75 / 100
 18000 ms 526108 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());

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

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;
		for(auto p : initial_cor) {
			if(on_treap.count(p.X))
				res.push_back({p.X, T->query(p.X)});
			else
				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) {
		P.push_back(new Points({{i, {x, y}}}, 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);

	vector<pair<int, ii> > P;
	for(int i = 1 ; i <= m ; i++) {
		int a, b;
		scanf("%d%d", &a, &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);
		if(t == 1) {
			int i;
			scanf("%d", &i);
			ii p = PP->query(i);
			printf("%d %d\n", p.X, p.Y);
		} else if(t == 2) {
			int s;
			scanf("%d", &s);
			PP->sweep_horizontally(s);
		} else if(t == 3) {
			int s;
			scanf("%d", &s);
			PP->sweep_vertically(s);
		} else {
			int a, b;
			scanf("%d%d", &a, &b);
			PP->add_point(++cnt, a, b);
		}
		
		//~ cout << "TREAP\n";
		//~ PP->T->print();
	}

	return 0;
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:389:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:394:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:404:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
sweeping.cpp:407:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &i);
    ~~~~~^~~~~~~~~~
sweeping.cpp:412:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &s);
    ~~~~~^~~~~~~~~~
sweeping.cpp:416:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &s);
    ~~~~~^~~~~~~~~~
sweeping.cpp:420:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3448 KB Output is correct
2 Correct 35 ms 1272 KB Output is correct
3 Correct 47 ms 2680 KB Output is correct
4 Correct 37 ms 3192 KB Output is correct
5 Correct 60 ms 2168 KB Output is correct
6 Correct 12 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17073 ms 483960 KB Output is correct
2 Correct 16886 ms 471860 KB Output is correct
3 Correct 16928 ms 471404 KB Output is correct
4 Correct 13034 ms 481036 KB Output is correct
5 Correct 14164 ms 479664 KB Output is correct
6 Correct 16559 ms 507080 KB Output is correct
7 Correct 16418 ms 467880 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6528 ms 408572 KB Output is correct
2 Correct 6465 ms 408580 KB Output is correct
3 Correct 5786 ms 397148 KB Output is correct
4 Correct 5663 ms 403808 KB Output is correct
5 Correct 5972 ms 404456 KB Output is correct
6 Correct 6290 ms 408672 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6528 ms 408572 KB Output is correct
2 Correct 6465 ms 408580 KB Output is correct
3 Correct 5786 ms 397148 KB Output is correct
4 Correct 5663 ms 403808 KB Output is correct
5 Correct 5972 ms 404456 KB Output is correct
6 Correct 6290 ms 408672 KB Output is correct
7 Correct 8180 ms 381604 KB Output is correct
8 Correct 8412 ms 381496 KB Output is correct
9 Correct 8157 ms 381428 KB Output is correct
10 Correct 7628 ms 397200 KB Output is correct
11 Correct 8713 ms 403928 KB Output is correct
12 Correct 9335 ms 404544 KB Output is correct
13 Correct 8847 ms 404472 KB Output is correct
14 Correct 518 ms 256 KB Output is correct
15 Correct 3540 ms 100472 KB Output is correct
16 Correct 8090 ms 379692 KB Output is correct
17 Correct 7731 ms 379608 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3448 KB Output is correct
2 Correct 35 ms 1272 KB Output is correct
3 Correct 47 ms 2680 KB Output is correct
4 Correct 37 ms 3192 KB Output is correct
5 Correct 60 ms 2168 KB Output is correct
6 Correct 12 ms 1024 KB Output is correct
7 Correct 17073 ms 483960 KB Output is correct
8 Correct 16886 ms 471860 KB Output is correct
9 Correct 16928 ms 471404 KB Output is correct
10 Correct 13034 ms 481036 KB Output is correct
11 Correct 14164 ms 479664 KB Output is correct
12 Correct 16559 ms 507080 KB Output is correct
13 Correct 16418 ms 467880 KB Output is correct
14 Correct 6528 ms 408572 KB Output is correct
15 Correct 6465 ms 408580 KB Output is correct
16 Correct 5786 ms 397148 KB Output is correct
17 Correct 5663 ms 403808 KB Output is correct
18 Correct 5972 ms 404456 KB Output is correct
19 Correct 6290 ms 408672 KB Output is correct
20 Correct 8180 ms 381604 KB Output is correct
21 Correct 8412 ms 381496 KB Output is correct
22 Correct 8157 ms 381428 KB Output is correct
23 Correct 7628 ms 397200 KB Output is correct
24 Correct 8713 ms 403928 KB Output is correct
25 Correct 9335 ms 404544 KB Output is correct
26 Correct 8847 ms 404472 KB Output is correct
27 Correct 518 ms 256 KB Output is correct
28 Correct 3540 ms 100472 KB Output is correct
29 Correct 8090 ms 379692 KB Output is correct
30 Correct 7731 ms 379608 KB Output is correct
31 Correct 12377 ms 451200 KB Output is correct
32 Correct 17188 ms 468516 KB Output is correct
33 Correct 9568 ms 410340 KB Output is correct
34 Execution timed out 18100 ms 526108 KB Time limit exceeded
35 Halted 0 ms 0 KB -