oj.uz

Submission #364921

# Submission time Handle Problem Language Result Execution time Memory
364921 2021-02-10T12:54:14 Z Kevin_Zhang_TW Sweeping (JOI20_sweeping) C++17
100 / 100
 13594 ms 278956 KB 
#undef KEV

#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 == -1 ? 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(-1, 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:91:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |   int M = L + R >> 1;
      |           ~~^~~
sweeping.cpp: In function 'void data::insertseg(int, int, int, int)':
sweeping.cpp:107:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp: In function 'std::pair<int, int> data::qry(int)':
sweeping.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
sweeping.cpp:143:3: note: in expansion of macro 'DE'
  143 |   DE(id, belong[id]);
      |   ^~
sweeping.cpp: In function 'void data::init_all()':
sweeping.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
sweeping.cpp:151:3: note: in expansion of macro 'DE'
  151 |   DE("cut");
      |   ^~
sweeping.cpp:18:20: warning: statement has no effect [-Wunused-value]
   18 | #define debug(...) 0
      |                    ^
sweeping.cpp:152:3: note: in expansion of macro 'debug'
  152 |   debug(cut, cut + cl);
      |   ^~~~~
sweeping.cpp: In function 'void data::modiseg(int, int, int, int, int)':
sweeping.cpp:157:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  157 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
sweeping.cpp:163:4: note: in expansion of macro 'DE'
  163 |    DE("chmnmx", nL, nR, cut[M], i);
      |    ^~
sweeping.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
sweeping.cpp:175:3: note: in expansion of macro 'DE'
  175 |   DE("Modi ", nL, nR, P, cut[M], i);
      |   ^~
sweeping.cpp: In function 'void cdqsolve(int, int)':
sweeping.cpp:292:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  292 |  int M = L + R >> 1;
      |          ~~^~~
sweeping.cpp:17:17: warning: statement has no effect [-Wunused-value]
   17 | #define DE(...) 0
      |                 ^
sweeping.cpp:296:2: note: in expansion of macro 'DE'
  296 |  DE(L, M, R);
      |  ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 138604 KB Output is correct
2 Correct 98 ms 138348 KB Output is correct
3 Correct 95 ms 138348 KB Output is correct
4 Correct 104 ms 138604 KB Output is correct
5 Correct 105 ms 138548 KB Output is correct
6 Correct 95 ms 138476 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11809 ms 237536 KB Output is correct
2 Correct 11760 ms 237636 KB Output is correct
3 Correct 11911 ms 241244 KB Output is correct
4 Correct 5523 ms 255148 KB Output is correct
5 Correct 8128 ms 252768 KB Output is correct
6 Correct 10770 ms 241556 KB Output is correct
7 Correct 11597 ms 236708 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9251 ms 240072 KB Output is correct
2 Correct 9188 ms 259740 KB Output is correct
3 Correct 4017 ms 263224 KB Output is correct
4 Correct 4980 ms 266472 KB Output is correct
5 Correct 8376 ms 262116 KB Output is correct
6 Correct 8055 ms 259820 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 9251 ms 240072 KB Output is correct
2 Correct 9188 ms 259740 KB Output is correct
3 Correct 4017 ms 263224 KB Output is correct
4 Correct 4980 ms 266472 KB Output is correct
5 Correct 8376 ms 262116 KB Output is correct
6 Correct 8055 ms 259820 KB Output is correct
7 Correct 12523 ms 245948 KB Output is correct
8 Correct 12994 ms 246320 KB Output is correct
9 Correct 12646 ms 245820 KB Output is correct
10 Correct 5938 ms 257636 KB Output is correct
11 Correct 8487 ms 260204 KB Output is correct
12 Correct 12926 ms 260832 KB Output is correct
13 Correct 12608 ms 265964 KB Output is correct
14 Correct 524 ms 153748 KB Output is correct
15 Correct 818 ms 201480 KB Output is correct
16 Correct 11896 ms 245296 KB Output is correct
17 Correct 11437 ms 236016 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 138604 KB Output is correct
2 Correct 98 ms 138348 KB Output is correct
3 Correct 95 ms 138348 KB Output is correct
4 Correct 104 ms 138604 KB Output is correct
5 Correct 105 ms 138548 KB Output is correct
6 Correct 95 ms 138476 KB Output is correct
7 Correct 11809 ms 237536 KB Output is correct
8 Correct 11760 ms 237636 KB Output is correct
9 Correct 11911 ms 241244 KB Output is correct
10 Correct 5523 ms 255148 KB Output is correct
11 Correct 8128 ms 252768 KB Output is correct
12 Correct 10770 ms 241556 KB Output is correct
13 Correct 11597 ms 236708 KB Output is correct
14 Correct 9251 ms 240072 KB Output is correct
15 Correct 9188 ms 259740 KB Output is correct
16 Correct 4017 ms 263224 KB Output is correct
17 Correct 4980 ms 266472 KB Output is correct
18 Correct 8376 ms 262116 KB Output is correct
19 Correct 8055 ms 259820 KB Output is correct
20 Correct 12523 ms 245948 KB Output is correct
21 Correct 12994 ms 246320 KB Output is correct
22 Correct 12646 ms 245820 KB Output is correct
23 Correct 5938 ms 257636 KB Output is correct
24 Correct 8487 ms 260204 KB Output is correct
25 Correct 12926 ms 260832 KB Output is correct
26 Correct 12608 ms 265964 KB Output is correct
27 Correct 524 ms 153748 KB Output is correct
28 Correct 818 ms 201480 KB Output is correct
29 Correct 11896 ms 245296 KB Output is correct
30 Correct 11437 ms 236016 KB Output is correct
31 Correct 7915 ms 251604 KB Output is correct
32 Correct 11621 ms 259044 KB Output is correct
33 Correct 10179 ms 227632 KB Output is correct
34 Correct 13544 ms 261568 KB Output is correct
35 Correct 13594 ms 261272 KB Output is correct
36 Correct 5957 ms 275184 KB Output is correct
37 Correct 9487 ms 278956 KB Output is correct
38 Correct 12160 ms 277916 KB Output is correct
39 Correct 12590 ms 277532 KB Output is correct
40 Correct 11210 ms 258344 KB Output is correct