Submission #721288

#	Time	Username	Problem	Language	Result	Execution time	Memory
721288		khshg	Plahte (COCI17_plahte)	C++14	160 / 160	717 ms	49060 KiB

plahte

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
using str = string;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second

template<class T> using V = vector<T>;
#define arr array
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)

template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }

const int maxn = 8e4 + 10;
int N, M, par[maxn], ans[maxn];
V<pair<pi, pi>> r;
V<pair<pi, int>> b;
map<int, int> cmpx, cmpy;
V<tuple<int, int, int, int, int>> events;
// x cordinate
// 0/2 - a sheet ; y cordinate ; length down ; id;
// 1 - a ball ; y cordinate ; color of the ball ; ignore this;
set<int> stl[maxn];
vi adj[maxn];

ll bit[3 * maxn];
void upd(int ind, int val) {
	while(ind < 3 * maxn) {
		bit[ind] += val;
		ind += ind & -ind;
	}
}
ll rino(int ind) {
	ll res = 0;
	while(ind > 0) {
		res += bit[ind];
		ind -= ind & -ind;
	}
	if(res < 0) {
		cout << "NO\n";
		exit(0);
	}
	return res;
}
void make(int y, int len, int id) {
	ll t = rino(y);
	upd(y + 1, t - id);
	upd(y - len, id - t);
}

void dfs(int s) {
	trav(u, adj[s]) {
		dfs(u);
		if(sz(stl[u]) > sz(stl[s])) swap(stl[u], stl[s]);
		trav(v, stl[u]) stl[s].ins(v);
	}
	ans[s] = sz(stl[s]);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> M;
	r.rsz(N);
	F0R(i, N) {
		cin >> r[i].ff.ff >> r[i].ff.ss >> r[i].ss.ff >> r[i].ss.ss;
		cmpx[r[i].ff.ff];
		cmpy[r[i].ff.ss];
		cmpx[r[i].ss.ff];
		cmpy[r[i].ss.ss];
	}
	b.rsz(M);
	F0R(i, M) {
		cin >> b[i].ff.ff >> b[i].ff.ss >> b[i].ss;
		cmpx[b[i].ff.ff];
		cmpy[b[i].ff.ss];
	}
	{
		int tim3 = 1;
		trav(u, cmpx) {
			u.ss = tim3++;
		}
		tim3 = 1;
		trav(u, cmpy) {
			u.ss = tim3++;
		}
		F0R(i, N) {
			r[i].ff.ff = cmpx[r[i].ff.ff];
			r[i].ff.ss = cmpy[r[i].ff.ss];
			r[i].ss.ff = cmpx[r[i].ss.ff];
			r[i].ss.ss = cmpy[r[i].ss.ss];
			events.eb(r[i].ff.ff, 0, r[i].ss.ss, r[i].ss.ss - r[i].ff.ss, i + 1);
			events.eb(r[i].ss.ff, 2, r[i].ss.ss, r[i].ss.ss - r[i].ff.ss, i + 1);
		}
		F0R(i, M) {
			b[i].ff.ff = cmpx[b[i].ff.ff];
			b[i].ff.ss = cmpy[b[i].ff.ss];
			events.eb(b[i].ff.ff, 1, b[i].ff.ss, b[i].ss, 0);
		}
	}
	sor(events);
	trav(u, events) {
		int x, y; int ball; int c; int id;
		tie(x, ball, y, c, id) = u;
		if(ball == 1) {
			stl[rino(y)].ins(c);
			continue;
		}
		if(ball == 2) {
			make(y, c, par[id]);
			continue;
		}
		par[id] = rino(y);
		make(y, c, id);
	}
	F0R(i, N) adj[par[i + 1]].pb(i + 1);
	dfs(0);
	F0R(i, N) cout << ans[i + 1] << '\n';
	return 0;
}

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32