Submission #88069

#	Time	Username	Problem	Language	Result	Execution time	Memory
88069		MAMBA	Sunčanje (COCI18_suncanje)	C++17	0 / 130	2453 ms	173348 KiB

suncanje

#ifdef _MSC_VER
#define __builtin_popcount (int)__popcnt
#define __builtin_popcountll (int)__popcnt64
#define __builtin_clz (int)__lzcnt
#define $ system("pause")
#else
#define $
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> point;

#define MOD ll(1e9 + 7)
#define MAXN int(2e5 + 20)
#define lg 17
#define inf int(2e9 + 100)

#define rep(i, j, k) for (int i = j; i < k; i++)
#define for_all(x) x.begin(), x.end()
#define lid id << 1
#define rid id << 1 | 1
#define lch l, mid, lid
#define rch mid, r, rid
#define pb push_back
#define X first
#define Y second
#define re real()
#define im imag()

template <typename S, typename T>
inline ostream &operator<<(ostream &out, const pair<S, T> &p)
{
	return out << "( " << p.X << " , " << p.Y << " )";
}
template <typename S>
inline ostream &operator<<(ostream &out, const vector<S> &p)
{
	for (auto &e : p) out << e << ' '; return out;
}
template <typename T, typename S> inline T
smin(T &a, const S &b) { return a > b ? a = b : a; }
template <typename T, typename S> inline T
smax(T &a, const S &b) { return a < b ? a = b : a; }
inline double dot(const point l, const point r) { return l.re * r.re + l.im * r.im; }
inline double cross(const point l, const point r) { return l.re * r.im - l.im * r.re; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }
#define int ll
#define pii pll
int n, m;
int arr[MAXN], x[MAXN], y[MAXN], a[MAXN], b[MAXN];
bool answer[MAXN];
struct Segment {
	set<pii> s;
	inline set<pii>::iterator get_itr(int r) {
		return s.lower_bound(pii(r, -100));
	}
	inline set<pii>::iterator get_itl(int l) {
		auto itl = s.lower_bound(pii(l, -100));
		if (itl != s.begin()) {
			auto it2 = itl; it2--;
			if ((*it2).Y > l)
				itl = it2;
		}
		return itl;
	}
	inline bool merge(int l, int r) {
		auto itr = get_itr(r);
		auto itl = get_itl(l);
		if (itl == itr) {
			s.insert(pii(l, r));
			return false;
		}
		smin(l, (*itl).X);
		itr--;
		smax(r, (*itr).Y);
		itr++;
		while (itl != itr) {
			auto it = itl;
			itl++;
			s.erase(it);
		}
		s.insert(pii(l, r));
		return true;
	}
	inline bool get(int l, int r) {
		return get_itl(l) != get_itr(r);
	}
} seg[MAXN * 4], seg2[MAXN * 4];

bool seg_add(int s, int t, int ss, int tt, int l = 0, int r = m, int id = 1) {
	if (l >= t || r <= s) return false;
	if (l >= s && r <= t) return (seg[id].merge(ss, tt) || seg2[id].merge(ss, tt));
	int mid = l + r >> 1;
	seg2[id].merge(ss, tt);
	return seg[id].get(ss, tt) || seg_add(s, t, ss, tt, lch) || seg_add(s, t, ss, tt, rch);
}

inline bool bad(int i, int j) {
	int l = max(x[i], x[j]);
	int r = min(x[i] + a[i], x[j] + a[j]);
	if (r <= l) return false;
	l = max(y[i], y[j]);
	r = min(y[i] + b[i], y[j] + b[j]);
	if (r <= l) return false;
	return true;
}

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	rep(i, 0, n) {
		cin >> x[i] >> y[i] >> a[i] >> b[i];
		arr[i << 1] = x[i];
		arr[i << 1 | 1] = x[i] + a[i] - 1;
	}
	sort(arr, arr + 2 * n);
	m = unique(arr, arr + 2 * n) - arr;
	for (int i = n - 1; ~i; i--) {
		int l = lower_bound(arr, arr + m, x[i]) - arr;
		int r = upper_bound(arr, arr + m, x[i] + a[i] - 1) - arr;
		answer[i] = seg_add(l, r, y[i], y[i] + b[i]);
	}
	rep(i, 0, n)
		cout << (answer[i] ? "NE\n" : "DA\n");
	$;
	return (0);
}

/*
4
0 0 1 2
0 4 1 2
0 1 1 4
0 3 1 10
*/

Compilation message (stderr)

suncanje.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
suncanje.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto &e : p) out << e << ' '; return out;
  ^~~
suncanje.cpp:47:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto &e : p) out << e << ' '; return out;
                                     ^~~~~~
suncanje.cpp: In function 'bool seg_add(ll, ll, ll, ll, ll, ll, ll)':
suncanje.cpp:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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