Submission #759254

# Submission time Handle Problem Language Result Execution time Memory
759254 2023-06-16T01:03:56 Z NK_ UFO (IZhO14_ufo) C++17
0 / 100
688 ms 104412 KB
#include <bits/stdc++.h>

using namespace std;

/////////////////////// MACROS ////////////////////////////////////////////
using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll,ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<str>;
using vc = vector<char>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcTU> using PR = pair<T,U>;
tcTU> using umap = unordered_map<T, U>;
tcT> using uset = unordered_set<T>;
tcT> using mset = multiset<T>;

#define mp make_pair
#define f first
#define s second

#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define ppb pop_back()
#define ppf pop_front()
#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

// LOOPS
#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 rep(a) F0R(_, a)
#define each(a,x) for (auto& a: x)

/////////////////////// IMPORANT VARS /////////////////////////////////////

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INFL = ll(3e18)+10;
const int INF = int(1e9)+10;
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
tcT> using pql = priority_queue<T,vector<T>,less<T>>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define nl '\n'

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { 
	return x == 0 ? 0 : 31-__builtin_clz(x); }
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }
 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
	auto it = t.find(u); assert(it != end(t));
	t.erase(it); } // element that doesn't exist from (multi)set


// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;

// tcT> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// #define ook order_of_key
// #define fbo find_by_order

// struct chash { 
// 	const uint64_t C = ll(2e18*PI)+71;
// 	const int RANDOM = rng();
// 	ll operator()(ll x) const {
// 		return __builtin_bswap64((x^RANDOM)*C); }
// };
// template<class K,class V> using um = unordered_map<K,V,chash>;
// template<class K,class V> using ht = gp_hash_table<K,V,chash>;
// template<class K,class V> V get(ht<K,V>& u, K x) {
// 	auto it = u.find(x); return it == end(u) ? 0 : it->s; }

/////////////////////// OUPUT /////////////////////////////////////////////
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
	#ifdef LOCAL
		return b ? "true" : "false";
	#else
		return ts((int)b);
	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")";
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}

tcTU> str ts(V<pair<T, U>> v) {
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
	#endif
}

tcT> str ts(T v) {
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}

///////////////////////// DEBUG ///////////////////////////////////////////
#define tcTUU tcT, class ...U
void DBG() { cerr << "]" << "\e[0m" << endl; }
tcTUU> void DBG(const T& t, const U&... u) {
	cerr << ts(t); if (sizeof...(u)) cerr << ", ";
	DBG(u...); }
#ifdef LOCAL
	#define dbg(...) cerr << "\e[1m" << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif	

///////////////////////// FILE I/O ////////////////////////////////////////
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setPrec() { cout << fixed << setprecision(15); }
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s = "") {
	unsyncIO(); setPrec();
	#ifndef LOCAL	
		if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for USACO
	#endif
}

///////////////////////// TEMPLATE ABOVE //////////////////////////////////

// REMEMBER
// - Don't Focus On Only One Approach
// - Read And Understand Problem Fully
// - Think Of Edges Cases
// - Implement Carefully
// - Always Check For Overflows
// - Reset Global Variables
// - Look At The Bigger Picture
// - Don't Get Discouraged, You Can Pull It Back

tcT> struct Seg { // comb(ID,b) = b
	const T ID = -INF; T comb(T a, T b) { return max(a, b); } 
	int n; V<T> seg;
	void init(int _n) { // upd, query also work if n = _n
		for (n = 1; n < _n; ) n *= 2; 
		// n = _n;
		seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void set(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] += val; for (p /= 2; p; p /= 2) pull(p); }

	int get(int p) { return seg[p += n]; }

	int first_at_least(int lo, int val, int ind, int l, int r) { // if seg stores max across range
		if (r <= lo || val > seg[ind]) return -1;
		if (l == r) return l;
		int m = (l+r)/2;
		int res = first_at_least(lo,val,2*ind,l,m); if (res != -1) return res;
		return first_at_least(lo,val,2*ind+1,m+1,r);
	}

	int get_first(int lo, int v) { return first_at_least(lo, v, 1, 0, n-1); }

	int last_at_least(int hi, int val, int ind, int l, int r) { // if seg stores max across range
		if (hi <= l || val > seg[ind]) return -1;
		if (l == r) return l;
		int m = (l+r)/2;
		int res = last_at_least(hi,val,2*ind+1,m+1,r); if (res != -1) return res;
		return last_at_least(hi,val,2*ind,l,m);
	}
	
	int get_last(int hi, int v) { return last_at_least(hi, v, 1, 0, n-1); }
};

void solve() {
	int N, M, T, K, X; cin >> N >> M >> T >> K >> X;

	V<Seg<int>> R(N), C(M); 
	F0R(i, N) R[i].init(M);
	F0R(i, M) C[i].init(N);

	F0R(i, N) {
		F0R(j, M) {
			int x; cin >> x;
			R[i].set(j, x);
			C[j].set(i, x);
		}
	}

	F0R(l_, K) {
		char dir; cin >> dir;
		dbg(l_, dir);
		if (dir == 'N') {
			int c, h; cin >> c >> h; --c;
			dbg(c, h);
			int cur = -1;

			rep(T) {
				int nxt = C[c].get_first(cur, h);
				if (nxt == -1) break;

				dbg(nxt, c, C[c].get(nxt), R[nxt].get(c));
				C[c].upd(nxt, -1);
				R[nxt].upd(c, -1);
				cur = nxt;
			}	
		}

		if (dir == 'S') {
			int c, h; cin >> c >> h; --c;
			dbg(c, h);
			int cur = N + 1;

			rep(T) {
				int nxt = C[c].get_last(cur, h);
				if (nxt == -1) break;

				dbg(nxt, c, C[c].get(nxt), R[nxt].get(c));
				C[c].upd(nxt, -1);
				R[nxt].upd(c, -1);
				cur = nxt;
			}
		}

		if (dir == 'W') {
			int r, h; cin >> r >> h; --r;
			dbg(r, h);
			int cur = -1;

			rep(T) {
				int nxt = R[r].get_first(cur, h);
				if (nxt == -1) break;

				dbg(r, nxt, R[r].get(nxt), C[nxt].get(r));
				R[r].upd(nxt, -1);
				C[nxt].upd(r, -1);
				cur = nxt;
			}
		}	

		if (dir == 'E') {
			int r, h; cin >> r >> h; --r;
			dbg(r, h);
			int cur = M + 1;

			rep(T) {
				int nxt = R[r].get_last(cur, h);
				if (nxt == -1) break;

				dbg(r, nxt, R[r].get(nxt), C[nxt].get(r));
				R[r].upd(nxt, -1);
				C[nxt].upd(r, -1);
				cur = nxt;
			}
		}
	}	

	V<vl> A(N, vl(M));
	F0R(i, N) F0R(j, M) {
		A[i][j] = R[i].get(j);
		assert(R[i].get(j) == C[j].get(i));
	}

	F0R(i, N) cout << ts(A[i]) << nl;


	V<vl> P(N+1, vl(M+1));
	FOR(i, 1, N+1) FOR(j, 1, M+1) {
		P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + A[i-1][j-1];
	}

	auto qry = [&](int r1, int c1, int r2, int c2) {
		return P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1];
	};

	ll ans = 0;
	FOR(r, 1, N+1) FOR(c, 1, M+1) if (r+X-1 <= N && c+X-1 <= M) {
		ckmax(ans, qry(r, c, r+X-1, c+X-1));
	}

	// cout << ans << nl;
}

int main() {
	setIO(); 

	int TT = 1;
	// cin >> TT;

	rep(TT) solve();
	
	exit(0-0);
}

Compilation message

ufo.cpp: In function 'void solve()':
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:275:3: note: in expansion of macro 'dbg'
  275 |   dbg(l_, dir);
      |   ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:278:4: note: in expansion of macro 'dbg'
  278 |    dbg(c, h);
      |    ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:285:5: note: in expansion of macro 'dbg'
  285 |     dbg(nxt, c, C[c].get(nxt), R[nxt].get(c));
      |     ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:294:4: note: in expansion of macro 'dbg'
  294 |    dbg(c, h);
      |    ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:301:5: note: in expansion of macro 'dbg'
  301 |     dbg(nxt, c, C[c].get(nxt), R[nxt].get(c));
      |     ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:310:4: note: in expansion of macro 'dbg'
  310 |    dbg(r, h);
      |    ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:317:5: note: in expansion of macro 'dbg'
  317 |     dbg(r, nxt, R[r].get(nxt), C[nxt].get(r));
      |     ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:326:4: note: in expansion of macro 'dbg'
  326 |    dbg(r, h);
      |    ^~~
ufo.cpp:194:19: warning: statement has no effect [-Wunused-value]
  194 |  #define dbg(...) 0
      |                   ^
ufo.cpp:333:5: note: in expansion of macro 'dbg'
  333 |     dbg(r, nxt, R[r].get(nxt), C[nxt].get(r));
      |     ^~~
ufo.cpp: In function 'void setIn(str)':
ufo.cpp:201:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ufo.cpp: In function 'void setOut(str)':
ufo.cpp:202:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 11 ms 724 KB Output isn't correct
5 Incorrect 52 ms 2852 KB Output isn't correct
6 Incorrect 134 ms 22088 KB Output isn't correct
7 Incorrect 227 ms 50808 KB Output isn't correct
8 Incorrect 173 ms 47156 KB Output isn't correct
9 Incorrect 300 ms 43952 KB Output isn't correct
10 Incorrect 381 ms 47148 KB Output isn't correct
11 Incorrect 272 ms 40480 KB Output isn't correct
12 Incorrect 386 ms 47164 KB Output isn't correct
13 Incorrect 469 ms 53360 KB Output isn't correct
14 Incorrect 339 ms 40624 KB Output isn't correct
15 Incorrect 381 ms 48036 KB Output isn't correct
16 Incorrect 175 ms 40604 KB Output isn't correct
17 Incorrect 610 ms 56900 KB Output isn't correct
18 Incorrect 180 ms 44960 KB Output isn't correct
19 Incorrect 248 ms 53348 KB Output isn't correct
20 Incorrect 688 ms 104412 KB Output isn't correct