Submission #161709

#	Time	Username	Problem	Language	Result	Execution time	Memory
161709		qkxwsm	Sunčanje (COCI18_suncanje)	C++14	130 / 130	2013 ms	149612 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 asdf
#define y2 ZXCV
#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 530013

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, M;
ppp arr[MAXN];
vi compress;
bitset<MAXN> ans;
set<pii> full[MAXN], part[MAXN];

bool trav(int w, int L, int R, int a, int b, pii p)
{
	// cerr << "TRAV " << L << ' ' << R << ' ' << a << ' ' << b << endl;
	bool res = false;
	auto it = full[w].LB({p.fi, -1});
	if (it != full[w].end() && it -> fi <= p.se) res = true;
	if (it != full[w].begin() && (prev(it) -> se) >= p.fi) res = true;
	if (a <= L && R <= b)
	{
		it = part[w].LB({p.fi, -1});
		if (it != part[w].end() && it -> fi <= p.se) res = true;
		if (it != part[w].begin() && (prev(it) -> se) >= p.fi) res = true;
	}
	//check with full[w]
	//part[w] merges with p
	int lt = p.fi, rt = p.se;
	it = part[w].LB({p.fi, -1});
	if (it != part[w].begin() && prev(it) -> se >= lt - 1)
	{
		it = prev(it); lt = it -> fi;
	}
	while(it != part[w].end() && it -> fi <= p.se + 1)
	{
		ckmax(rt, it -> se); it = part[w].erase(it);
	}
	part[w].insert({lt, rt});
	if (a <= L && R <= b)
	{
		lt = p.fi; rt = p.se;
		it = full[w].LB({p.fi, -1});
		if (it != full[w].begin() && prev(it) -> se >= lt - 1)
		{
			it = prev(it); lt = it -> fi;
		}
		while(it != full[w].end() && it -> fi <= p.se + 1)
		{
			ckmax(rt, it -> se); it = full[w].erase(it);
		}
		full[w].insert({lt, rt});
		return res;
		//check with partial[w]
		//full[w] merges with p
	}
	int mid = (L + R) >> 1;
	if (a <= mid)
	{
		res |= trav(w << 1, L, mid, a, b, p);
	}
	if (mid < b)
	{
		res |= trav(w << 1 | 1, mid + 1, R, a, b, p);
	}
	return res;
}

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 - 1);
		swap(arr[i].fi.se, arr[i].se.fi);
		compress.PB(arr[i].fi.fi); compress.PB(arr[i].fi.se);
	}
	sort(ALL(compress)); compress.erase(unique(ALL(compress)), compress.end());
	FOR(i, 0, N)
	{
		arr[i].fi.fi = LB(ALL(compress), arr[i].fi.fi) - compress.begin();
		arr[i].fi.se = LB(ALL(compress), arr[i].fi.se) - compress.begin() - 1;
	}
	M = SZ(compress);
	FORD(i, N, 0)
	{
		ans[i] = trav(1, 0, M - 1, arr[i].fi.fi, arr[i].fi.se, arr[i].se);
		//so there's a full and a partial thing.
		//a full is: it affects all the crap in ur child. this thing is a PART of ur range.
		//a partial is: it affects evreything containing it. this thing shares something with ur range.
	}
	FOR(i, 0, N)
	{
		cout << (ans[i] ? "NE" : "DA") << '\n';
	}
}

• 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