Submission #364915

# Submission time Handle Problem Language Result Execution time Memory
364915 2021-02-10T12:47:39 Z Kevin_Zhang_TW Sweeping (JOI20_sweeping) C++17
0 / 100
773 ms 279916 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 {
	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];
 
	int belong[MAX_Q + MAX_N];
 
	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) {
		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();
	}
 
	// must be modified well already
	
	void insertseg(int id, int L = 0, int R = cl - 1, int i = 1) {
		if (L > R) return;
		const auto &[l, r] = dust[id];
		int M = L + R >> 1, mid = cut[ M ];

		++cnt[i];
 
		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);
	}
 
	bool chmnmx(pair<int,int> &loc, int L, int R) {
		bool res = chmax(loc.first, L);
		res |= chmin(loc.second, R);
		return res;
		//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) {
		assert(ok[id]);
		auto res = dust[id];
		DE(id, belong[id]);
		if (belong[id]) {
			chmnmx(res, treeLR[belong[id]]);
		}
		return res;
	}
 
	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;
 
		if ((P == nR && P >= mid) ||
			(P == nL && P <= mid)) {
			chmnmx(treeLR[i], nL, nR);
			DE("chmnmx", nL, nR, cut[M], i);
		}
 
		++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) {
						assert(false);
						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 {
				assert(P < mid && P == nR);
				auto &pq = linex[i];
				while (pq.size()) {
					if (dust[ pq.top() ].first > P) break;
					int id = pq.top();
					if (belong[id] != i) {
						assert(false);
						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);
 
					chmin(dust[id].second, P);
 
					kill(id);
 
					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) {
		static int hcnt[MAX_N + MAX_Q];
		int id = qid[qd];
		if (ok[id]) {
			assert(++hcnt[qd] == 1);
			ans[qd] = qry(id);
		}
	}
}
 
 
void mody(int L) {
	data::modiseg(0, L);
}
void modx(int L) {
	data::modiseg(L, inf);
}
 
void cdqsolve(int L, int R) {



	for (int i = L;i <= R;++i) if (qt[i] == ad_t) {
		data::init_tree();
		int id = data::create_dust(qx[i], qy[i]);
		DE(id);
		data::addseg(id);
		for (int j = i + 1;j <= R;++j) {
			DE(j, qt[j], qL[j]);
			if (qt[j] == qry_t)
				data::updateans(j);
			if (qt[j] == modx_t)
				modx(qL[j]);
			if (qt[j] == mody_t)
				mody(qL[j]);
		}
	}

	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);
 
	{
		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] == modx_t)
				modx(qL[i]);
			if (qt[i] == mody_t)
				mody(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;
	if (m > 2000) return 1;
 
	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;

	chmax(cl, 1);

	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:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |   int M = L + R >> 1;
      |           ~~^~~
sweeping.cpp: In function 'void data::insertseg(int, int, int, int)':
sweeping.cpp:105:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp: In function 'std::pair<int, int> data::qry(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:141:3: note: in expansion of macro 'DE'
  141 |   DE(id, belong[id]);
      |   ^~
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:149:3: note: in expansion of macro 'DE'
  149 |   DE("cut");
      |   ^~
sweeping.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
sweeping.cpp:150:3: note: in expansion of macro 'debug'
  150 |   debug(cut, cut + cl);
      |   ^~~~~
sweeping.cpp: In function 'void data::modiseg(int, int, int, int, int)':
sweeping.cpp:155:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |   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:161:4: note: in expansion of macro 'DE'
  161 |    DE("chmnmx", nL, nR, cut[M], i);
      |    ^~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:173:3: note: in expansion of macro 'DE'
  173 |   DE("Modi ", nL, nR, P, cut[M], i);
      |   ^~
sweeping.cpp: In function 'void cdqsolve(int, int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:265:3: note: in expansion of macro 'DE'
  265 |   DE(id);
      |   ^~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:268:4: note: in expansion of macro 'DE'
  268 |    DE(j, qt[j], qL[j]);
      |    ^~
sweeping.cpp:290:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  290 |  int M = L + R >> 1;
      |          ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:294:2: note: in expansion of macro 'DE'
  294 |  DE(L, M, R);
      |  ^~
# Verdict Execution time Memory Grader output
1 Correct 727 ms 138348 KB Output is correct
2 Correct 329 ms 138348 KB Output is correct
3 Correct 193 ms 138476 KB Output is correct
4 Correct 773 ms 138456 KB Output is correct
5 Runtime error 316 ms 279916 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 122476 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 122348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 122348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 727 ms 138348 KB Output is correct
2 Correct 329 ms 138348 KB Output is correct
3 Correct 193 ms 138476 KB Output is correct
4 Correct 773 ms 138456 KB Output is correct
5 Runtime error 316 ms 279916 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -