Submission #161545

#	Time	Username	Problem	Language	Result	Execution time	Memory
161545		qkxwsm	Sunčanje (COCI18_suncanje)	C++14	0 / 130	2085 ms	59388 KiB

suncanje

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define y1 what
#define y2 chard
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 140013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, pii> ppp;

int N;
ppp arr[MAXN];
vi xs, ys;
bitset<MAXN> ans;
vector<pair<pii, int> > ql[MAXN], qr[MAXN], del[MAXN], ins[MAXN];
int lazy[4 * MAXN];
pii stor[4 * MAXN];
set<pair<pii, int> > fw, bw;

pii comb(pii a, pii b)
{
	if (a.fi < b.fi) return a;
	if (a.fi > b.fi) return b;
	return {a.fi, a.se + b.se};
}
void build(int w, int L, int R)
{
	stor[w] = {0, R - L + 1};
	lazy[w] = 0;
	if (L == R) return;
	int mid = (L + R) >> 1;
	build(w << 1, L, mid);
	build(w << 1 | 1, mid + 1, R);
}
void push(int w, int L, int R)
{
	if (lazy[w] == 0);
	stor[w].fi += lazy[w];
	if (L != R)
	{
		lazy[w << 1] += lazy[w];
		lazy[w << 1 | 1] += lazy[w];
	}
	lazy[w] = 0;
	return;
}
void update(int w, int L, int R, int a, int b, int v)
{
	// cerr << L << ' ' << R << ' ' << a << ' ' << b << ' ' << v << endl;
	push(w, L, R);
	if (b < L || R < a) return;
	if (a <= L && R <= b)
	{
		lazy[w] += v;
		push(w, L, R);
		return;
	}
	int mid = (L + R) >> 1;
	update(w << 1, L, mid, a, b, v);
	update(w << 1 | 1, mid + 1, R, a, b, v);
	stor[w] = comb(stor[w << 1], stor[w << 1 | 1]);
}
pii query(int w, int L, int R, int a, int b)
{
	push(w, L, R);
	if (a <= L && R <= b)
	{
		return stor[w];
	}
	int mid = (L + R) >> 1;
	if (b <= mid) return query(w << 1, L, mid, a, b);
	if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
	return comb(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}

void solve(int L, int R)
{
	if (L == R) return;
	int mid = (L + R) >> 1;
	solve(L, mid);
	solve(mid + 1, R);
	// cerr << "SOLVE " << L << ' ' << R << endl;
	xs.clear(); ys.clear();
	FOR(i, L, R + 1)
	{
		xs.PB(arr[i].fi.fi); ys.PB(arr[i].fi.se); xs.PB(arr[i].se.fi); ys.PB(arr[i].se.se);
	}
	// cerr << SZ(xs) << ' ' << SZ(ys) << endl;
	sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end());
	sort(ALL(ys)); ys.erase(unique(ALL(ys)), ys.end());
	// cerr << SZ(xs) << ' ' << SZ(ys) << endl;
	FOR(i, 0, SZ(xs))
	{
		ql[i].clear(); qr[i].clear(); ins[i].clear(); del[i].clear();
	}
	FOR(i, L, mid + 1)
	{
		int x1 = LB(ALL(xs), arr[i].fi.fi) - xs.begin();
		int y1 = LB(ALL(ys), arr[i].fi.se) - ys.begin();
		int x2 = LB(ALL(xs), arr[i].se.fi) - xs.begin() - 1;
		int y2 = LB(ALL(ys), arr[i].se.se) - ys.begin() - 1;
		ql[x1].PB({{y1, y2}, i});
		qr[x2].PB({{y1, y2}, i});
		// cerr << x2 << " WITHIN " << SZ(xs) << endl;
		// cerr << "query " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
		//these are the guys that query.
	}
	FOR(i, mid + 1, R + 1)
	{
		int x1 = LB(ALL(xs), arr[i].fi.fi) - xs.begin();
		int y1 = LB(ALL(ys), arr[i].fi.se) - ys.begin();
		int x2 = LB(ALL(xs), arr[i].se.fi) - xs.begin() - 1;
		int y2 = LB(ALL(ys), arr[i].se.se) - ys.begin() - 1;
		ins[x1].PB({{y1, y2}, i});
		del[x2].PB({{y1, y2}, i});
		// cerr << "send " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
		//these are the guys that send.
	}
	build(1, 0, SZ(ys) - 1);
	FOR(i, 0, SZ(xs))
	{
		// cerr << "YES\n";
		// cerr << SZ(ins[i]) << endl;
		for (auto a : ins[i])
		{
			// cerr << "ALIVE\n";
			// cerr << "KILLER " << a.fi.fi << ' ' << a.fi.se << endl;
			update(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se, 1);
			int lo = a.fi.fi, hi = a.fi.se;
			auto it = fw.LB({{lo, -1}, -1});
			while(it != fw.end() && it -> fi.fi <= hi)
			{
				// cerr << it -> fi.fi << endl;
				ans[it -> se] = true;
				bw.erase({{it -> fi.se, it -> fi.fi}, it -> se});
				it = fw.erase(it);
			}
			auto jt = bw.LB({{hi + 1, -1}, -1});
			while(jt != bw.begin() && (prev(jt) -> fi.fi >= lo))
			{
				jt = prev(jt);
				ans[jt -> se] = true;
				bw.erase({{jt -> fi.se, jt -> fi.fi}, jt -> se});
				jt = bw.erase(jt);
			}
		}
		for (auto a : ql[i])
		{
			int idx = a.se;
			pii p = query(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se);
			if (p.fi != 0 || p.se != (a.fi.se - a.fi.fi + 1))
			{
				ans[idx] = true;
			}
			fw.insert({a.fi, idx});
			bw.insert({{a.fi.se, a.fi.fi}, idx});
		}
		for (auto a : qr[i])
		{
			int idx = a.se;
			pii p = query(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se);
			if (p.fi != 0 || p.se != (a.fi.se - a.fi.fi + 1))
			{
				ans[idx] = true;
			}
			if (fw.find(a) != fw.end())
			{
				fw.erase({a.fi, idx});
				bw.erase({{a.fi.se, a.fi.fi}, idx});
			}
		}
		for (auto a : del[i])
		{
			update(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se, -1);
		}
	}
	//either it overlaps on the left, or it overlaps on the right, or it is completely contained
	//use the print segtree to solve the noraml case.
	//otherwise the killer has to be inside the query.
	//then we have a bunc hof query rectangles, and then
	//so when you have a killer rectangle become alive, you just use the set.
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	cin >> N;
	FOR(i, 0, N)
	{
		cin >> arr[i].fi.fi >> arr[i].fi.se >> arr[i].se.fi >> arr[i].se.se;
		arr[i].se.fi += (arr[i].fi.fi);
		arr[i].se.se += (arr[i].fi.se);
	}
	//update this rectangle.
	//ehh seems hard.
	//update r5 with 5. then update r4 with 4. then update r3 with 3.
	//then if any point in rect x is updated with > x then you lose.
	//OR
	//in decreasing order of rectangles, update every point in a rectangle by 1.
	//then for a given rectangle, query if there's anything on in it.
	//bleh, you can like, store ranges of ok guys.
	//the ndoe in the segtree stores, THERE'S AT LEAST ONE GUY IN HERE WITH THIS.
	//then when you update x you don't even need to worry about its children.
	solve(0, N - 1);
	FOR(i, 0, N)
	{
		cout << (ans[i] ? "NE" : "DA") << '\n';
	}
	return 0;
}

• 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