Submission #636554

#	Time	Username	Problem	Language	Result	Execution time	Memory
636554		vovamr	Sunčanje (COCI18_suncanje)	C++17	130 / 130	3597 ms	192692 KiB

suncanje

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct fenw {
	int n;
	ve<ve<int>> que;
	ve<ve<int>> fe;
	fenw(int s) : n(s + 10) { que.resize(n); fe.resize(n); }
	inline void pupd(int x, int y) { x += 3; for (; x < n; x += x & -x) que[x].pb(y); }
	inline void pget(int x, int y) { if(x<0||y<0){return;} x += 3; for (; x; x -= x & -x) que[x].pb(y); }
	inline void pget(int x0, int x1, int y0, int y1) {
		if (x0 > x1 || y0 > y1) return;
		pget(x1, y1);
		pget(x0 - 1, y1);
		pget(x1, y0 - 1);
		pget(x0 - 1, y0 - 1);
	}
	inline void prep() {
		for (int i = 0; i < n; ++i) {
			sort(all(que[i]));
			que[i].erase(unique(all(que[i])), que[i].end());
			fe[i].resize(sz(que[i]) + 10);
		}
	}

	inline void upd(int x, int y, int d) {
		x += 3;
		for (; x < n; x += x & -x) {
			int i = lower_bound(all(que[x]), y) - que[x].begin() + 3;
			for (; i < sz(fe[x]); i += i & -i) fe[x][i] += d;
		}
	}
	inline int get(int x, int y) {
		if (x < 0 || y < 0) return 0;
		x += 3; int ans = 0;
		for (; x; x -= x & -x) {
			int i = lower_bound(all(que[x]), y) - que[x].begin() + 3;
			for (; i; i -= i & -i) ans += fe[x][i];
		} return ans;
	}
	inline int get(int x0, int x1, int y0, int y1) {
		if (x0 > x1 || y0 > y1) return 0;
		return get(x1, y1) - get(x0 - 1, y1) - get(x1, y0 - 1) + get(x0 - 1, y0 - 1);
	}
};

struct fenw1d {
	int n;
	ve<int> fe;
	fenw1d(int s) : n(s + 10) { fe.resize(n); }
	inline void upd(int i, int x) { i += 3; for (; i < n; i += i & -i) fe[i] += x; }
	inline int get(int i) { i += 3; int ans = 0; for (; i; i -= i & -i){ans+=fe[i];} return ans; }
	inline int get(int l, int r) { if(l>r){return 0;} return get(r) - get(l - 1); }
};

inline void solve() {
	int n;
	cin >> n;
	ve<array<int,4>> a(n);
	for (auto &[a, b, c, d] : a) cin >> a >> b >> c >> d;

	ve<int> alx, aly;
	for (int i = 0; i < n; ++i) {
		auto &[x, y, dx, dy] = a[i];

		int x0 = x, x1 = x + dx - 1;
		int y0 = y, y1 = y + dy - 1;

		alx.pb(x0), alx.pb(x1);
		aly.pb(y0), aly.pb(y1);
	}
	sort(all(alx)), sort(all(aly));
	alx.erase(unique(all(alx)), alx.end());
	aly.erase(unique(all(aly)), aly.end());

	int m = sz(alx), my = sz(aly);

	for (int i = 0; i < n; ++i) {
		auto &[x, y, dx, dy] = a[i];

		int x0 = x, x1 = x + dx - 1;
		int y0 = y, y1 = y + dy - 1;

		x0 = lower_bound(all(alx), x0) - alx.begin();
		x1 = lower_bound(all(alx), x1) - alx.begin();

		y0 = lower_bound(all(aly), y0) - aly.begin();
		y1 = lower_bound(all(aly), y1) - aly.begin();

		a[i] = {x0, y0, x1, y1};
	}

	fenw right_down(m);
	fenw left_down(m);
	fenw right_up(m);
	fenw left_up(m);

	fenw1d left(my);
	fenw1d right(my);

	fenw1d up(m);
	fenw1d down(m);

	reverse(all(a));

	for (auto &[x0, y0, x1, y1] : a) {
		right_down.pupd(x1, y1);
		left_down.pupd(x1, y0);
		right_up.pupd(x0, y1);
		left_up.pupd(x0, y0);

		right_down.pget(x0 - 1, y0 - 1);
		left_up.pget(x1 + 1, m - 1, y1 + 1, my - 1);
		right_up.pget(x1 + 1, m - 1, 0, y0 - 1);
		left_down.pget(0, x0 - 1, y1 + 1, my - 1);
	}

	right_down.prep();
	left_down.prep();
	right_up.prep();
	left_up.prep();

	ve<int> res(n); int ptr = n - 1, cnt = 0;
	for (auto &[x0, y0, x1, y1] : a) {

		right_down.upd(x1, y1, +1);
		left_down.upd(x1, y0, +1);
		right_up.upd(x0, y1, +1);
		left_up.upd(x0, y0, +1);

		right.upd(y1, +1);
		left.upd(y0, +1);

		down.upd(x1, +1);
		up.upd(x0, +1);

		int ans = 0;

		ans += right.get(y0 - 1);
		ans += left.get(y1 + 1, my - 1);

		ans += down.get(x0 - 1);
		ans += up.get(x1 + 1, m - 1);
		
		ans -= right_down.get(x0 - 1, y0 - 1);
		ans -= left_up.get(x1 + 1, m - 1, y1 + 1, my - 1);
		ans -= right_up.get(x1 + 1, m - 1, 0, y0 - 1);
		ans -= left_down.get(0, x0 - 1, y1 + 1, my - 1);

		res[ptr--] = (ans == cnt), ++cnt;
	}

	for (auto &i : res) cout << (i ? "DA" : "NE") << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
/**
5
1 1 4 2
6 1 1 1
2 2 2 3
3 4 3 2
4 0 1 2
*/

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13