oj.uz

Submission #212350

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

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) {
		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 38 ms 3320 KB Output is correct
2 Correct 33 ms 1148 KB Output is correct
3 Correct 42 ms 2552 KB Output is correct
4 Correct 37 ms 3064 KB Output is correct
5 Correct 56 ms 2168 KB Output is correct
6 Correct 10 ms 896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16520 ms 470056 KB Output is correct
2 Correct 16358 ms 471024 KB Output is correct
3 Correct 16466 ms 470144 KB Output is correct
4 Correct 12565 ms 480492 KB Output is correct
5 Correct 13658 ms 479788 KB Output is correct
6 Correct 16447 ms 506456 KB Output is correct
7 Correct 15927 ms 467460 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6040 ms 408792 KB Output is correct
2 Correct 5804 ms 408896 KB Output is correct
3 Correct 5137 ms 397128 KB Output is correct
4 Correct 5078 ms 403792 KB Output is correct
5 Correct 5666 ms 404768 KB Output is correct
6 Correct 5744 ms 408892 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6040 ms 408792 KB Output is correct
2 Correct 5804 ms 408896 KB Output is correct
3 Correct 5137 ms 397128 KB Output is correct
4 Correct 5078 ms 403792 KB Output is correct
5 Correct 5666 ms 404768 KB Output is correct
6 Correct 5744 ms 408892 KB Output is correct
7 Correct 7672 ms 381524 KB Output is correct
8 Correct 8425 ms 381388 KB Output is correct
9 Correct 8545 ms 381284 KB Output is correct
10 Correct 7841 ms 397044 KB Output is correct
11 Correct 8505 ms 403576 KB Output is correct
12 Correct 8843 ms 404840 KB Output is correct
13 Correct 8449 ms 404520 KB Output is correct
14 Correct 276 ms 376 KB Output is correct
15 Correct 3110 ms 100596 KB Output is correct
16 Correct 7596 ms 379764 KB Output is correct
17 Correct 7206 ms 379748 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3320 KB Output is correct
2 Correct 33 ms 1148 KB Output is correct
3 Correct 42 ms 2552 KB Output is correct
4 Correct 37 ms 3064 KB Output is correct
5 Correct 56 ms 2168 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 16520 ms 470056 KB Output is correct
8 Correct 16358 ms 471024 KB Output is correct
9 Correct 16466 ms 470144 KB Output is correct
10 Correct 12565 ms 480492 KB Output is correct
11 Correct 13658 ms 479788 KB Output is correct
12 Correct 16447 ms 506456 KB Output is correct
13 Correct 15927 ms 467460 KB Output is correct
14 Correct 6040 ms 408792 KB Output is correct
15 Correct 5804 ms 408896 KB Output is correct
16 Correct 5137 ms 397128 KB Output is correct
17 Correct 5078 ms 403792 KB Output is correct
18 Correct 5666 ms 404768 KB Output is correct
19 Correct 5744 ms 408892 KB Output is correct
20 Correct 7672 ms 381524 KB Output is correct
21 Correct 8425 ms 381388 KB Output is correct
22 Correct 8545 ms 381284 KB Output is correct
23 Correct 7841 ms 397044 KB Output is correct
24 Correct 8505 ms 403576 KB Output is correct
25 Correct 8843 ms 404840 KB Output is correct
26 Correct 8449 ms 404520 KB Output is correct
27 Correct 276 ms 376 KB Output is correct
28 Correct 3110 ms 100596 KB Output is correct
29 Correct 7596 ms 379764 KB Output is correct
30 Correct 7206 ms 379748 KB Output is correct
31 Correct 12057 ms 450960 KB Output is correct
32 Correct 16922 ms 468312 KB Output is correct
33 Correct 9224 ms 409964 KB Output is correct
34 Execution timed out 18087 ms 513748 KB Time limit exceeded
35 Halted 0 ms 0 KB -