oj.uz

Submission #211513

# Submission time Handle Problem Language Result Execution time Memory
211513 2020-03-20T16:31:08 Z Benq Sweeping (JOI20_sweeping) C++14
100 / 100
 6542 ms 329720 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 1500005; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
	bool fst = 1; str res = "{";
	F0R(i,sz(v)) {
		if (!fst) res += ", ";
		fst = 0; res += ts(v[i]);
	}
	res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class T> str ts(T v) {
	bool fst = 1; str res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
	return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

int par[2*MX];

struct DSU {
	vi val; vector<vi> rpar;
	void init() { val.clear(); rpar.clear(); }
	int ad(int v, int label) {
		int ind = sz(val); 
		val.pb(v); rpar.eb();
		if (label != -1) {
			par[label] = ind;
			rpar.bk.pb(label);
		}
		return ind;
	}
	int merge(int x, int y) {
		assert(x != y);
		if (sz(rpar[x]) < sz(rpar[y])) swap(x,y);
		val[x] = max(val[x],val[y]);
		trav(t,rpar[y]) par[t] = x, rpar[x].pb(t);
		return x;
	}
	int getVal(int x) { return val[par[x]]; }
};
DSU D;

struct cmp {
	bool operator()(const int& a, const int& b) { return D.val[a] > D.val[b]; }
};
int xpos[MX], ypos[MX];
pi getPos(int x) { return {D.getVal(2*x),D.getVal(2*x+1)}; }

int N,M,Q;
bool done[MX];
pi ans[MX], pos[MX];

void solve(int x, int y, vector<array<int,3>> v) {
	if (!sz(v)) return;
	int dif = N-x-y;
	if (dif == 0) {
		trav(t,v) if (t[0] == 1) ans[t[2]] = {x,y};
		return;
	}
	D.init(); 
	int X = x+(dif+1)/2, Y = y+dif/2+1; // either >= X or >= Y, not both
	vector<array<int,3>> UP, RI;
	priority_queue<int,vi,cmp> px, py;
	trav(t,v) {
		if (t[0] == 1) {
			if (pos[t[1]].s >= Y) UP.pb(t);
			else if (pos[t[1]].f >= X) RI.pb(t);
			else ans[t[2]] = getPos(t[1]);
		} else if (t[0] == 2) { // H
			if (t[1] >= Y) {
				// move everything in px <= N-t[1] to the right
				int z = N-t[1]; int nex = D.ad(z,-1);
				while (sz(px) && D.val[px.top()] < z) {
					int x = px.top(); px.pop();
					nex = D.merge(nex,x);
				}
				px.push(nex); UP.pb(t);
			} else { // kill everything py <= t[1]
				while (sz(py) && D.val[py.top()] <= t[1]) {
					int x = py.top(); py.pop(); 
					trav(u,D.rpar[x]) {
						u /= 2;
						if (!done[u]) {
							pos[u] = getPos(u); pos[u].f = N-t[1]; 
							done[u] = 1; RI.pb({4,u,-1});
						}
					}
				}
				RI.pb(t);
			}
		} else if (t[0] == 3) { // V
			if (t[1] >= X) {
				int z = N-t[1]; int nex = D.ad(z,-1);
				while (sz(py) && D.val[py.top()] < z) {
					int x = py.top(); py.pop();
					nex = D.merge(nex,x);
				}
				py.push(nex); RI.pb(t);
			} else {
				while (sz(px) && D.val[px.top()] <= t[1]) {
					int x = px.top(); px.pop(); 
					trav(u,D.rpar[x]) {
						u /= 2;
						if (!done[u]) {
							pos[u] = getPos(u); pos[u].s = N-t[1]; 
							done[u] = 1; UP.pb({4,u,-1});
						}
					}
				}
				UP.pb(t);
			}
		} else if (t[0] == 4) {
			done[t[1]] = 0; pi p = pos[t[1]];
			if (p.s >= Y) done[t[1]] = 1, UP.pb(t);
			else if (p.f >= X) done[t[1]] = 1, RI.pb(t);
			else {
				px.push(D.ad(p.f,2*t[1]));
				py.push(D.ad(p.s,2*t[1]+1));
			}
		}
	}
	solve(x,Y,UP); solve(X,y,RI);
}

int main() {
	setIO(); re(N,M,Q);
	int cnt = 0;
	vector<array<int,3>> todo;
	F0R(i,M) {
		int x,y; re(x,y);
		pos[++cnt] = {x,y};
		todo.pb({4,cnt,0});
	}
	F0R(i,Q) {
		ans[i] = {-1,-1};
		int t; re(t);
		if (t <= 3) {
			int p; re(p);
			todo.pb({t,p,i});
		} else {
			int a,b; re(a,b);
			pos[++cnt] = {a,b};
			todo.pb({t,cnt,i});
		}
	}
	solve(0,0,todo);
	F0R(i,Q) if (ans[i] != mp(-1,-1)) ps(ans[i].f,ans[i].s);
	// you should actually read the stuff at the bottom
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Compilation message

sweeping.cpp: In function 'void setIn(std::__cxx11::string)':
sweeping.cpp:123:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp: In function 'void setOut(std::__cxx11::string)':
sweeping.cpp:124:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1152 KB Output is correct
2 Correct 22 ms 896 KB Output is correct
3 Correct 11 ms 1024 KB Output is correct
4 Correct 22 ms 1228 KB Output is correct
5 Correct 19 ms 1336 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5055 ms 129196 KB Output is correct
2 Correct 4715 ms 127264 KB Output is correct
3 Correct 4051 ms 127000 KB Output is correct
4 Correct 3555 ms 189492 KB Output is correct
5 Correct 6487 ms 148440 KB Output is correct
6 Correct 6200 ms 164160 KB Output is correct
7 Correct 4422 ms 125996 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3528 ms 146672 KB Output is correct
2 Correct 3650 ms 148208 KB Output is correct
3 Correct 2996 ms 174640 KB Output is correct
4 Correct 3815 ms 270984 KB Output is correct
5 Correct 3580 ms 220364 KB Output is correct
6 Correct 3598 ms 148680 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3528 ms 146672 KB Output is correct
2 Correct 3650 ms 148208 KB Output is correct
3 Correct 2996 ms 174640 KB Output is correct
4 Correct 3815 ms 270984 KB Output is correct
5 Correct 3580 ms 220364 KB Output is correct
6 Correct 3598 ms 148680 KB Output is correct
7 Correct 3748 ms 139772 KB Output is correct
8 Correct 4330 ms 142540 KB Output is correct
9 Correct 4306 ms 135472 KB Output is correct
10 Correct 4046 ms 170184 KB Output is correct
11 Correct 4487 ms 233508 KB Output is correct
12 Correct 5759 ms 185276 KB Output is correct
13 Correct 6373 ms 299772 KB Output is correct
14 Correct 162 ms 51656 KB Output is correct
15 Correct 1043 ms 100740 KB Output is correct
16 Correct 3488 ms 144432 KB Output is correct
17 Correct 3872 ms 150568 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1152 KB Output is correct
2 Correct 22 ms 896 KB Output is correct
3 Correct 11 ms 1024 KB Output is correct
4 Correct 22 ms 1228 KB Output is correct
5 Correct 19 ms 1336 KB Output is correct
6 Correct 11 ms 1024 KB Output is correct
7 Correct 5055 ms 129196 KB Output is correct
8 Correct 4715 ms 127264 KB Output is correct
9 Correct 4051 ms 127000 KB Output is correct
10 Correct 3555 ms 189492 KB Output is correct
11 Correct 6487 ms 148440 KB Output is correct
12 Correct 6200 ms 164160 KB Output is correct
13 Correct 4422 ms 125996 KB Output is correct
14 Correct 3528 ms 146672 KB Output is correct
15 Correct 3650 ms 148208 KB Output is correct
16 Correct 2996 ms 174640 KB Output is correct
17 Correct 3815 ms 270984 KB Output is correct
18 Correct 3580 ms 220364 KB Output is correct
19 Correct 3598 ms 148680 KB Output is correct
20 Correct 3748 ms 139772 KB Output is correct
21 Correct 4330 ms 142540 KB Output is correct
22 Correct 4306 ms 135472 KB Output is correct
23 Correct 4046 ms 170184 KB Output is correct
24 Correct 4487 ms 233508 KB Output is correct
25 Correct 5759 ms 185276 KB Output is correct
26 Correct 6373 ms 299772 KB Output is correct
27 Correct 162 ms 51656 KB Output is correct
28 Correct 1043 ms 100740 KB Output is correct
29 Correct 3488 ms 144432 KB Output is correct
30 Correct 3872 ms 150568 KB Output is correct
31 Correct 3973 ms 166596 KB Output is correct
32 Correct 4027 ms 137384 KB Output is correct
33 Correct 4101 ms 116980 KB Output is correct
34 Correct 4295 ms 147724 KB Output is correct
35 Correct 4265 ms 138496 KB Output is correct
36 Correct 3912 ms 169180 KB Output is correct
37 Correct 6542 ms 299996 KB Output is correct
38 Correct 5938 ms 329720 KB Output is correct
39 Correct 5173 ms 268400 KB Output is correct
40 Correct 3473 ms 154372 KB Output is correct