Submission #364777

#	Time	Username	Problem	Language	Result	Execution time	Memory
364777		Kevin_Zhang_TW	Sweeping (JOI20_sweeping)	C++17	1 / 100	123 ms	14176 KiB

sweeping

#undef KEV
#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 MAX_N = 500010, MAX_Q = 1000010;
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);
}
pair<int,int> qry(int id) {
	return trans(dust[id]);
}
void mody(int L) {
	for (auto &[x, y] : dust)
		if (x <= L) chmin(y, L);
}
void modx(int L) {
	for (auto &[x, y] : dust)
		if (y >= L) chmax(x, L);
}

void add_dust(int x, int y) {
	dust.pb(trans(x, y));
}

int qt[MAX_Q], qid[MAX_Q], qL[MAX_Q], qx[MAX_Q], qy[MAX_Q];

const int qry_t = 1, mody_t = 3, modx_t = 2, ad_t = 4;

int cut[MAX_Q], cl;



int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> W >> m >> q;
	dust.resize(m);
	for (auto &[x, y] : dust)
		cin >> x >> y;
if (m > 2000) return 1; 
	for (auto &p : dust) p = trans(p);

	for (int i = 0, t;i < 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];
	}
	sort(cut, cut + cl);

	for (int i = 0, t, x, y;i < q;++i) {
		DE(qt[i], qid[i], qL[i], qx[i], qy[i]);
		t = qt[i];
		// qry dust id
		if (t == qry_t) {
			tie(x, y) = qry(qid[i]);
			cout << x << ' ' << y << '\n';
		}
		// do H
		if (t == mody_t)
			mody(qL[i]);
		// doV
		if (t == modx_t)
			modx(qL[i]);
		// add dust
		if (t == ad_t) 
			add_dust(qx[i], qy[i]);

//		for (auto p : dust) {
//			tie(x, y) = trans(p);
//			DE(x, y);
//		}
//		cerr << endl;
	}
}

Compilation message (stderr)

sweeping.cpp: In function 'int32_t main()':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:83:3: note: in expansion of macro 'DE'
   83 |   DE(qt[i], qid[i], qL[i], qx[i], qy[i]);
      |   ^~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25