oj.uz

Submission #212364

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

bool on_treap[2000007];
int nxt[2000007];

bool comp(pair<int, ii> &a, pair<int, ii> &b) {
	return a.Y < b.Y;
}

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, ii> initial_cor;
	map<int, int> M;
	
	Points(vector<pair<int, ii> > &P, int n) {
		this->n = n;
		T = new Treap();
		ST = new SegmentTree(inf);
		sort(P.begin(), P.end(), comp);
		for(int i = 0 ; i < P.size() ; i++) {
			initial_cor[P[i].X] = P[i].Y;
			if(i + 1 < P.size() && P[i + 1].Y.X == P[i].Y.X)
				nxt[P[i].X] = P[i + 1].X;
			else
				nxt[P[i].X] = -1;
			if(i == 0 || P[i - 1].Y.X < P[i].Y.X) {
				ST->insert(P[i].Y.X, P[i].Y.Y);
				M[P[i].Y.X] = P[i].X;
			}
		}
		m = P.size();
	}
	
	~Points() {
		for(auto p : initial_cor)
			on_treap[p.X] = 0;
		delete T;
		delete ST;
	}
	
	ii query(int i) {
		if(on_treap[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], n - s, initial_cor[M[x]].Y);
			on_treap[M[x]] = 1;
			M[x] = nxt[M[x]];
			int v = inf;
			if(M[x] != -1)
				v = initial_cor[M[x]].Y;
			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], x, n - s);
			on_treap[M[x]] = 1;
			M[x] = nxt[M[x]];
			int v = inf;
			if(M[x] != -1)
				v = initial_cor[M[x]].Y;
			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[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 constructor 'Points::Points(std::vector<std::pair<int, std::pair<int, int> > >&, int)':
sweeping.cpp:300:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < P.size() ; i++) {
                   ~~^~~~~~~~~~
sweeping.cpp:302:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i + 1 < P.size() && P[i + 1].Y.X == P[i].Y.X)
       ~~~~~~^~~~~~~~~~
sweeping.cpp: In member function 'void MasterPoints::add_point(int, int, int)':
sweeping.cpp:404: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 29 ms 3072 KB Output is correct
2 Correct 24 ms 1024 KB Output is correct
3 Correct 26 ms 2176 KB Output is correct
4 Correct 28 ms 2808 KB Output is correct
5 Correct 44 ms 1656 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 14001 ms 412236 KB Output is correct
2 Correct 13802 ms 412944 KB Output is correct
3 Correct 13967 ms 412444 KB Output is correct
4 Correct 11085 ms 416388 KB Output is correct
5 Correct 11952 ms 414404 KB Output is correct
6 Correct 14059 ms 437132 KB Output is correct
7 Correct 13472 ms 410156 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5477 ms 356600 KB Output is correct
2 Correct 5448 ms 356700 KB Output is correct
3 Correct 4686 ms 344748 KB Output is correct
4 Correct 4435 ms 351540 KB Output is correct
5 Correct 4947 ms 352476 KB Output is correct
6 Correct 5243 ms 356596 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5477 ms 356600 KB Output is correct
2 Correct 5448 ms 356700 KB Output is correct
3 Correct 4686 ms 344748 KB Output is correct
4 Correct 4435 ms 351540 KB Output is correct
5 Correct 4947 ms 352476 KB Output is correct
6 Correct 5243 ms 356596 KB Output is correct
7 Correct 7592 ms 336648 KB Output is correct
8 Correct 7384 ms 336720 KB Output is correct
9 Correct 7368 ms 336628 KB Output is correct
10 Correct 7048 ms 345076 KB Output is correct
11 Correct 8016 ms 351352 KB Output is correct
12 Correct 8633 ms 352252 KB Output is correct
13 Correct 8424 ms 352320 KB Output is correct
14 Correct 274 ms 376 KB Output is correct
15 Correct 3330 ms 92996 KB Output is correct
16 Correct 7367 ms 335380 KB Output is correct
17 Correct 6898 ms 335468 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3072 KB Output is correct
2 Correct 24 ms 1024 KB Output is correct
3 Correct 26 ms 2176 KB Output is correct
4 Correct 28 ms 2808 KB Output is correct
5 Correct 44 ms 1656 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 14001 ms 412236 KB Output is correct
8 Correct 13802 ms 412944 KB Output is correct
9 Correct 13967 ms 412444 KB Output is correct
10 Correct 11085 ms 416388 KB Output is correct
11 Correct 11952 ms 414404 KB Output is correct
12 Correct 14059 ms 437132 KB Output is correct
13 Correct 13472 ms 410156 KB Output is correct
14 Correct 5477 ms 356600 KB Output is correct
15 Correct 5448 ms 356700 KB Output is correct
16 Correct 4686 ms 344748 KB Output is correct
17 Correct 4435 ms 351540 KB Output is correct
18 Correct 4947 ms 352476 KB Output is correct
19 Correct 5243 ms 356596 KB Output is correct
20 Correct 7592 ms 336648 KB Output is correct
21 Correct 7384 ms 336720 KB Output is correct
22 Correct 7368 ms 336628 KB Output is correct
23 Correct 7048 ms 345076 KB Output is correct
24 Correct 8016 ms 351352 KB Output is correct
25 Correct 8633 ms 352252 KB Output is correct
26 Correct 8424 ms 352320 KB Output is correct
27 Correct 274 ms 376 KB Output is correct
28 Correct 3330 ms 92996 KB Output is correct
29 Correct 7367 ms 335380 KB Output is correct
30 Correct 6898 ms 335468 KB Output is correct
31 Correct 9613 ms 396676 KB Output is correct
32 Correct 13898 ms 409884 KB Output is correct
33 Correct 7550 ms 368608 KB Output is correct
34 Execution timed out 18115 ms 493444 KB Time limit exceeded
35 Halted 0 ms 0 KB -