oj.uz

답안 #364874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364874 2021-02-10T10:32:22 Z Kevin_Zhang_TW 청소 (JOI20_sweeping) C++17
10 / 100
 11979 ms 256052 KB 
#include <bits/extc++.h>
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; }
template<class T> bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; }
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int qry_t = 1, mody_t = 3, modx_t = 2, ad_t = 4;
const int MAX_N = 500010, MAX_Q = 1000010, inf = 1e9 + 7, QK = 20;

int m, q, W;

vector<pair<int,int>> dust;

pair<int,int> trans(int x, int y) { 
	return {x, W - y};
}
pair<int,int> trans(pair<int,int> d) {
	return trans(d.first, d.second);
}
int cut[MAX_Q], cl;

int qt[MAX_Q + MAX_N], qid[MAX_Q + MAX_N], qL[MAX_Q + MAX_N], qx[MAX_Q + MAX_N], qy[MAX_Q + MAX_N];
pair<int,int> ans[MAX_Q + MAX_N];

#define priority_queue __gnu_pbds::priority_queue
namespace data {
	vector<int> belong;
	//vector<int> lineon[2 << QK];
	struct cmpx { bool operator()(int a, int b) const { return dust[a].first > dust[b].first; } };
	struct cmpy { bool operator()(int a, int b) const { return dust[a].second < dust[b].second; } };
			// small comes out
	//priority_queue<int, vector<int>, cmpx> linex[2 << QK];
	priority_queue<int, cmpx> linex[2 << QK];
			// big comes out
	//priority_queue<int, vector<int>, cmpy> liney[2 << QK];
	priority_queue<int, cmpy> liney[2 << QK];

	priority_queue<int, cmpx>::point_iterator px[MAX_Q + MAX_N];
	priority_queue<int, cmpy>::point_iterator py[MAX_Q + MAX_N];

	pair<int,int> treeLR[2 << QK];

	bool ok[MAX_N + MAX_Q];
	vector<int> inside;

	int cnt[2 << QK];

	int create_dust(int x, int y) {
		belong.pb(0);
		dust.pb(x, y);
		return dust.size() - 1;
	}

	void putin(int sid, int tid) {
		belong[sid] = tid;
		px[sid] = linex[tid].push(sid);
		py[sid] = liney[tid].push(sid);
	}

	void dfsclear(int L = 0, int R = cl - 1, int i = 1) {
		if (cnt[i] == 0) return;
		treeLR[i] = treeLR[0], cnt[i] = 0;

//		priority_queue<int, vector<int>, cmpx>().swap(linex[i]);
//		priority_queue<int, vector<int>, cmpy>().swap(liney[i]);
		priority_queue<int, cmpx>().swap(linex[i]);
		priority_queue<int, cmpy>().swap(liney[i]);
		if (L == R) return;

		int M = L + R >> 1;
		dfsclear(L, M, i<<1), dfsclear(M+1, R, i<<1|1);
	}

	void init_tree() {
		dfsclear();
		for (int i : inside) 
			ok[i] = false, belong[i] = 0;
		inside.clear();
	}

	void insertseg(int id, int L = 0, int R = cl - 1, int i = 1) {
		const auto &[l, r] = dust[id];
		int M = L + R >> 1, mid = cut[ M ];
		++cnt[i];

		DE(l, r, mid);

		if (l <= mid && r >= mid) {
			putin(id, i);
			return;
		}
		if (L == R) {
			belong[id] = 0;
			return;
		}

		if (l < mid) insertseg(id, L, M, i << 1);
		else		 insertseg(id, M+1, R, i << 1|1);
	}

	void addseg(int id) {
		inside.pb(id);
		ok[id] = true;
		insertseg(id);

		DE(dust[id].first, dust[id].second);
	}

	bool chmnmx(pair<int,int> &loc, int L, int R) {
		return chmax(loc.first, L) || chmin(loc.second, R);
	}
	bool chmnmx(pair<int,int> &loc, pair<int,int> p) {
		return chmnmx(loc, p.first, p.second);
	}

	pair<int,int> qry(int id) {
		int mas = belong[id];
		if (mas) {
			chmnmx(dust[id], treeLR[ mas ].first, treeLR[ mas ].second);
		}
		//DE(id, belong[id], dust[id].first, dust[id].second);
		return dust[id];
	}

	void init_all() {
		DE("cut");
		debug(cut, cut + cl);
		fill(treeLR, treeLR + (MAX_Q << 1), make_pair(0, inf));
	}

	void modiseg(int nL, int nR, int L = 0, int R = cl - 1, int i = 1) {
		int M = L + R >> 1, mid = cut[ M ];
		int P = nL == 0 ? nR : nL;
		
		DE(nL, nR, P, cut[M], i);

		if ((nL == 0 && P >= mid)
				||
			(nL != 0 && P <= mid))
			chmnmx(treeLR[i], nL, nR);

		++cnt[i];

		auto kill = [&](int id) {
			linex[i].erase(px[id]);
			liney[i].erase(py[id]);
		};

		if (nL >= mid || nR <= mid) {

		DE("Modi ", nL, nR, P, cut[M], i);

			// nL == 0 means that now is R bound
			// need to take max y
			vector<int> reinsert;
			if (P == nL) {
				auto &pq = liney[i];
				while (pq.size()) {
					if (dust[ pq.top() ].second < P) break;
					int id = pq.top();
					if (belong[id] != i) {
						pq.pop();
						continue;
					}
					if (chmnmx(dust[id], treeLR[i])) {
						liney[i].modify(py[id], id);
						linex[i].modify(px[id], id);
						continue;
					}
					assert(dust[id].first <= P && dust[id].second >= P);

					chmax(dust[id].first, P);

					kill(id);

					reinsert.pb(id);
				}
			}
			else {
				auto &pq = linex[i];
				while (pq.size()) {
					if (dust[ pq.top() ].first > P) break;
					int id = pq.top();
					if (belong[id] != i) {
						pq.pop();
						continue;
					}
					if (chmnmx(dust[id], treeLR[i])) {
						liney[i].modify(py[id], id);
						linex[i].modify(px[id], id);
						continue;
					}

					if (dust[id].first > P || dust[id].second < P) {
						pq.push(id);
						continue;
					}

					assert(dust[id].first <= P && dust[id].second >= P);

					kill(id);

					chmin(dust[id].second, P);

					reinsert.pb(id);
				}
			}

			for (int id : reinsert) 
				insertseg(id, L, R, i);
		}

		if (L == R || P == mid) return;

		if (P < mid)
			modiseg(nL, nR, L, M, i<<1);
		else
			modiseg(nL, nR, M+1,R,i<<1|1);
	}

	void updateans(int qd) {
		int id = qid[qd];
		if (ok[id]) {
			ans[qd] = qry(id);
		}
	}
}


void mody(int L) {
	DE(0, L);
	data::modiseg(0, L);
//	for (auto &[x, y] : dust)
//		if (x <= L) chmin(y, L);
}
void modx(int L) {
	DE(L, inf);
	data::modiseg(L, inf);
//	for (auto &[x, y] : dust)
//		if (y >= L) chmax(x, L);
}


void cdqsolve(int L, int R) {
//	// m is dust cnt in the beggining
//	if (R < m) return;
//
//
//
////
////
//	for (int i = 0;i < m;++i) 
//		qid[i] = data::create_dust(qx[i], qy[i]);
//	for (int i = 0;i < m;++i)
//		data::addseg(qid[i]);
//		
//	for (int i = m;i <= R;++i) {
//		if (qt[i] == qry_t) 
//			data::updateans(i);
//		if (qt[i] == mody_t)
//			mody(qL[i]);
//		if (qt[i] == modx_t)
//			modx(qL[i]);
//	}
//
//
////
////
////
////
//	return;
	if (L == R) {
		if (qt[L] == ad_t) 
			qid[L] = data::create_dust(qx[L], qy[L]);

		return;
	}

	int M = L + R >> 1;

	cdqsolve(L, M);

	DE(L, M, R);

	if (true) {
		data::init_tree();
		for (int i = L;i <= M;++i) if (qt[i] == ad_t) {
			data::addseg(qid[i]);
		}
		for (int i = M+1;i <= R;++i) {
			if (qt[i] == qry_t)
				data::updateans(i);
			if (qt[i] == mody_t)
				mody(qL[i]);
			if (qt[i] == modx_t)
				modx(qL[i]);
		}
		for (int i = L;i <= M;++i) if (qt[i] == ad_t) 
			dust[ qid[i] ] = data::qry(qid[i]);
	}

	cdqsolve(M+1, R);
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> W >> m >> q;

	for (int i = 0;i < m;++i) {
		qt[i] = ad_t;
		cin >> qx[i] >> qy[i];
		tie(qx[i], qy[i]) = trans(qx[i], qy[i]);

		qid[i] = i;
	}

	for (int i = m, t;i < m + q;++i) {
		cin >> qt[i]; t = qt[i];
		// qry dust id
		if (t == qry_t) {
			cin >> qid[i]; --qid[i];
		}
		if (t == mody_t || t == modx_t){
			cin >> qL[i];
			if (t == modx_t) qL[i] = W - qL[i];
			cut[cl++] = qL[i];
		}
		// add dust
		if (t == 4) {
			cin >> qx[i] >> qy[i];
			tie(qx[i], qy[i]) = trans(qx[i], qy[i]);
		}
	}

	sort(cut, cut + cl);

	cl = unique(cut, cut + cl) - cut;

	data::init_all();

	cdqsolve(0, m + q - 1);

	for (int i = m;i < m + q;++i) {
		if (qt[i] == qry_t) {
			ans[i] = trans(ans[i]);
			auto [x, y] = ans[i];
			cout << x << ' ' << y << '\n';
		}
	}
}

Compilation message

sweeping.cpp: In function 'void data::dfsclear(int, int, int)':
sweeping.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int M = L + R >> 1;
      |           ~~^~~
sweeping.cpp: In function 'void data::insertseg(int, int, int, int)':
sweeping.cpp:99:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:102:3: note: in expansion of macro 'DE'
  102 |   DE(l, r, mid);
      |   ^~
sweeping.cpp: In function 'void data::addseg(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:122:3: note: in expansion of macro 'DE'
  122 |   DE(dust[id].first, dust[id].second);
      |   ^~
sweeping.cpp: In function 'void data::init_all()':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:142:3: note: in expansion of macro 'DE'
  142 |   DE("cut");
      |   ^~
sweeping.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
sweeping.cpp:143:3: note: in expansion of macro 'debug'
  143 |   debug(cut, cut + cl);
      |   ^~~~~
sweeping.cpp: In function 'void data::modiseg(int, int, int, int, int)':
sweeping.cpp:148:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:151:3: note: in expansion of macro 'DE'
  151 |   DE(nL, nR, P, cut[M], i);
      |   ^~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:167:3: note: in expansion of macro 'DE'
  167 |   DE("Modi ", nL, nR, P, cut[M], i);
      |   ^~
sweeping.cpp: In function 'void mody(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:247:2: note: in expansion of macro 'DE'
  247 |  DE(0, L);
      |  ^~
sweeping.cpp: In function 'void modx(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:253:2: note: in expansion of macro 'DE'
  253 |  DE(L, inf);
      |  ^~
sweeping.cpp: In function 'void cdqsolve(int, int)':
sweeping.cpp:295:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  295 |  int M = L + R >> 1;
      |          ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:299:2: note: in expansion of macro 'DE'
  299 |  DE(L, M, R);
      |  ^~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 138732 KB Output is correct
2 Incorrect 104 ms 138348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11979 ms 235552 KB Output is correct
2 Correct 11746 ms 238804 KB Output is correct
3 Correct 11855 ms 238492 KB Output is correct
4 Correct 5381 ms 256052 KB Output is correct
5 Correct 11131 ms 253448 KB Output is correct
6 Correct 11511 ms 247872 KB Output is correct
7 Correct 11976 ms 237540 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9259 ms 236544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9259 ms 236544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 138732 KB Output is correct
2 Incorrect 104 ms 138348 KB Output isn't correct
3 Halted 0 ms 0 KB -