oj.uz

Submission #212344

# Submission time Handle Problem Language Result Execution time Memory
212344 2020-03-22T17:44:24 Z mieszko11b Sweeping (JOI20_sweeping) C++14
75 / 100
 17006 ms 2097156 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 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;
	}
	
	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();
	}
	
	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();
			P.pop_back();
			auto P2 = P.back()->get_all_points();
			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:365: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:370: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:380:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
sweeping.cpp:383:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &i);
    ~~~~~^~~~~~~~~~
sweeping.cpp:388:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &s);
    ~~~~~^~~~~~~~~~
sweeping.cpp:392:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &s);
    ~~~~~^~~~~~~~~~
sweeping.cpp:396: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 11128 KB Output is correct
2 Correct 38 ms 9080 KB Output is correct
3 Correct 56 ms 16120 KB Output is correct
4 Correct 37 ms 9720 KB Output is correct
5 Correct 56 ms 12792 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16751 ms 1955892 KB Output is correct
2 Correct 16350 ms 1976388 KB Output is correct
3 Correct 16123 ms 1976228 KB Output is correct
4 Correct 12445 ms 1871936 KB Output is correct
5 Correct 13580 ms 1764172 KB Output is correct
6 Correct 15508 ms 1992908 KB Output is correct
7 Correct 16070 ms 1964764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6763 ms 428788 KB Output is correct
2 Correct 7180 ms 411312 KB Output is correct
3 Correct 5904 ms 399436 KB Output is correct
4 Correct 6202 ms 406440 KB Output is correct
5 Correct 6335 ms 407184 KB Output is correct
6 Correct 6768 ms 411220 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6763 ms 428788 KB Output is correct
2 Correct 7180 ms 411312 KB Output is correct
3 Correct 5904 ms 399436 KB Output is correct
4 Correct 6202 ms 406440 KB Output is correct
5 Correct 6335 ms 407184 KB Output is correct
6 Correct 6768 ms 411220 KB Output is correct
7 Correct 8480 ms 383992 KB Output is correct
8 Correct 8829 ms 383868 KB Output is correct
9 Correct 8475 ms 383816 KB Output is correct
10 Correct 7873 ms 399488 KB Output is correct
11 Correct 8891 ms 406140 KB Output is correct
12 Correct 9618 ms 407184 KB Output is correct
13 Correct 9289 ms 407320 KB Output is correct
14 Correct 498 ms 4216 KB Output is correct
15 Correct 3720 ms 114804 KB Output is correct
16 Correct 8346 ms 382096 KB Output is correct
17 Correct 8077 ms 382340 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11128 KB Output is correct
2 Correct 38 ms 9080 KB Output is correct
3 Correct 56 ms 16120 KB Output is correct
4 Correct 37 ms 9720 KB Output is correct
5 Correct 56 ms 12792 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct
7 Correct 16751 ms 1955892 KB Output is correct
8 Correct 16350 ms 1976388 KB Output is correct
9 Correct 16123 ms 1976228 KB Output is correct
10 Correct 12445 ms 1871936 KB Output is correct
11 Correct 13580 ms 1764172 KB Output is correct
12 Correct 15508 ms 1992908 KB Output is correct
13 Correct 16070 ms 1964764 KB Output is correct
14 Correct 6763 ms 428788 KB Output is correct
15 Correct 7180 ms 411312 KB Output is correct
16 Correct 5904 ms 399436 KB Output is correct
17 Correct 6202 ms 406440 KB Output is correct
18 Correct 6335 ms 407184 KB Output is correct
19 Correct 6768 ms 411220 KB Output is correct
20 Correct 8480 ms 383992 KB Output is correct
21 Correct 8829 ms 383868 KB Output is correct
22 Correct 8475 ms 383816 KB Output is correct
23 Correct 7873 ms 399488 KB Output is correct
24 Correct 8891 ms 406140 KB Output is correct
25 Correct 9618 ms 407184 KB Output is correct
26 Correct 9289 ms 407320 KB Output is correct
27 Correct 498 ms 4216 KB Output is correct
28 Correct 3720 ms 114804 KB Output is correct
29 Correct 8346 ms 382096 KB Output is correct
30 Correct 8077 ms 382340 KB Output is correct
31 Correct 11617 ms 1922860 KB Output is correct
32 Correct 17006 ms 1966532 KB Output is correct
33 Correct 9104 ms 1907436 KB Output is correct
34 Runtime error 11084 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -