Submission #93870

#	Time	Username	Problem	Language	Result	Execution time	Memory
93870		szawinis	Sunčanje (COCI18_suncanje)	C++17	104 / 130	3387 ms	263168 KiB

suncanje

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct Fenwick {
	vector<int> f;
	Fenwick() {}
	Fenwick(int n) {
		f.resize(n + 10);
	}
	void update(int i, int v) {
		++i;
		while(i < f.size()) f[i] += v, i += i & -i;
	}
	int query(int i) {
		++i;
		int ret = 0;
		while(i > 0) ret += f[i], i -= i & -i;
		return ret;
	}
};

struct MST {
	int n;
	vector<vector<int> > ls;
	vector<Fenwick> t;
	MST() {}
	MST(int n): n(n) {
		ls.resize(4*n);
		t.resize(4*n);
	}
	void clear() {
		t.clear();
		t = vector<Fenwick>(4*n);
	}
	void add_value(int x, int y) {
		for(x += n; x >= 1; x >>= 1) ls[x].push_back(y);
	}
//	void build(int i, int l, int r) {
//		cout << i << ' ' << l << ' ' << r << ' ' << ls[i].size() << ' ' << 2*n << endl;
//		sort(ls[i].begin(), ls[i].end());
//		ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
//		t[i] = Fenwick(ls[i].size());
//		if(l == r) return;
//		int mid = l+r >> 1;
//		build(i << 1, l, mid);
//		build(i << 1 | 1, mid+1, r);
//	}
	void build() {
		for(int i = 2*n-1; i >= 1; i--) {
			sort(ls[i].begin(), ls[i].end());
			ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
			t[i] = Fenwick(ls[i].size());
		}
	}
	void update(int x, int y) {
		for(x += n; x >= 1; x >>= 1) {
			auto it = lower_bound(ls[x].begin(), ls[x].end(), y);
			assert(it != ls[x].end());
			t[x].update(it - ls[x].begin(), 1);
		}
	}
	int query(int x1, int y1, int x2, int y2) {
		int ret = 0;
		for(x1 += n, x2 += n+1; x1 < x2; x1 >>= 1, x2 >>= 1) {
			if(x1 & 1) {
				auto ity1 = lower_bound(ls[x1].begin(), ls[x1].end(), y1);
				auto ity2 = upper_bound(ls[x1].begin(), ls[x1].end(), y2);
//				cout << ity2 - ity1 << ' ' << y1 << ' ' << y2 << ' ' << t[x1].query(t[x1].f.size() - 2) << endl;
				if(!ls[x1].empty() && ity1 != ls[x1].end() && ity2 != ls[x1].begin()) {
					--ity2;
					--ity1;
					assert(!t[x1].f.empty());
					ret += t[x1].query(ity2 - ls[x1].begin()) - t[x1].query(ity1 - ls[x1].begin());
				}
				++x1;
			}
			if(x2 & 1) {
				--x2;
				auto ity1 = lower_bound(ls[x2].begin(), ls[x2].end(), y1);
				auto ity2 = upper_bound(ls[x2].begin(), ls[x2].end(), y2);
//				cout << ity2 - ity1 << ' ' << y1 << ' ' << y2 << ' ' << t[x2].query(t[x2].f.size() - 2) << endl;
				if(!ls[x2].empty() && ity1 != ls[x2].end() && ity2 != ls[x2].begin()) {
					--ity2;
					--ity1;
					assert(!t[x2].f.empty());
					ret += t[x2].query(ity2 - ls[x2].begin()) - t[x2].query(ity1 - ls[x2].begin());
				}
			}
		}
		return ret;
	}
};

class Suncanje {

	int n;
	vector<tuple<int,int,int,int> > a;
	vector<int> res;
	vector<string> ans;
	MST mst[4];
	Fenwick fen[4];

	vector<int> xs, ys;
	void compress() {
		for(int i = 0, x1, y1, x2, y2; i < n; i++) {
			tie(x1, y1, x2, y2) = a[i];
			xs.push_back(x1);
			xs.push_back(x2);
			ys.push_back(y1);
			ys.push_back(y2);
		}
		sort(xs.begin(), xs.end());
		xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
		sort(ys.begin(), ys.end());
		ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
//		for(int x: xs) cout << x << ' ';
//		cout << endl;
//		for(int y: ys) cout << y << ' ';
//		cout << endl;
		for(auto &tt: a) {
			int x1, y1, x2, y2;
			tie(x1, y1, x2, y2) = tt;
			auto it = lower_bound(xs.begin(), xs.end(), x1);
			get<0>(tt) = it - xs.begin();
			it = lower_bound(xs.begin(), xs.end(), x2);
			get<2>(tt) = it - xs.begin();
			it = lower_bound(ys.begin(), ys.end(), y1);
			get<1>(tt) = it - ys.begin();
			it = lower_bound(ys.begin(), ys.end(), y2);
			get<3>(tt) = it - ys.begin();
//			cout << x1 << ' ' << y1 << ' ' <<x2 << ' ' << y2 << endl;
		}
//		for(auto &tt: a) {
//			int x1, y1, x2, y2;
//			tie(x1, y1, x2, y2) = tt;
//			cout << x1 << ' ' << y1 << ' ' <<x2 << ' ' << y2 << endl;
//		}
	}

public:
	void solve(istream &cin, ostream &cout) {
		cin >> n;
		for(int i = 0, x1, y1, A, B; i < n; i++) {
			cin >> x1 >> y1 >> A >> B;
			a.emplace_back(x1, y1, x1 + A, y1 + B);
		}
		res.resize(n);
		compress();
		reverse(a.begin(), a.end());
		int sz = max(xs.size(), ys.size());
		for(int i = 0; i < 4; i++) {
			mst[i] = MST(sz);
			fen[i] = Fenwick(sz);
		}
		for(auto tt: a) {
			int x1, y1, x2, y2;
			tie(x1, y1, x2, y2) = tt;
			mst[0].add_value(x1, y1);
			mst[1].add_value(x1, y2);
			mst[2].add_value(x2, y1);
			mst[3].add_value(x2, y2);
		}
		for(int i = 0; i < 4; i++) mst[i].build();

		for(int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			tie(x1, y1, x2, y2) = a[i];
//			cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;

			int pos = 0, neg = 0;
			pos += fen[2].query(x1) + i - fen[0].query(x2 - 1);
			pos += fen[3].query(y1) + i - fen[1].query(y2 - 1);

			neg += mst[0].query(x2, y2, sz - 1, sz - 1);
			neg += mst[1].query(x2, 0, sz - 1, y1);
			neg += mst[2].query(0, y2, x1, sz - 1);
			neg += mst[3].query(0, 0, x1, y1);

			res[i] = pos - neg;
//			cout << n-i << ' ' << pos << ' ' << neg << ' ' << res[i] << endl;
//			cout << fen[2].query(x1) << ' ' << fen[0].query(x2 - 1) << endl;
//			cout << fen[3].query(y1) << ' ' << fen[1].query(y2 - 1) << endl;

			fen[0].update(x1, 1);
			fen[1].update(y1, 1);
			fen[2].update(x2, 1);
			fen[3].update(y2, 1);

			mst[0].update(x1, y1);
			mst[1].update(x1, y2);
			mst[2].update(x2, y1);
			mst[3].update(x2, y2);

			ans.push_back((res[i] == i ? "DA" : "NE"));
		}

		reverse(ans.begin(), ans.end());
		for(string s: ans) cout << s << '\n';

	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
	    Suncanje *obj = new Suncanje();
		obj->solve(in, out);
		delete obj;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message (stderr)

suncanje.cpp: In member function 'void Fenwick::update(int, int)':
suncanje.cpp:23:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i < f.size()) f[i] += v, i += i & -i;
         ~~^~~~~~~~~~

• 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: 0 / 13
• Subtask 10: 0 / 13