Submission #40166

#	Time	Username	Problem	Language	Result	Execution time	Memory
40166		alanm	Plahte (COCI17_plahte)	C++14	0 / 160	510 ms	55500 KiB

plahte

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <math.h>
#include <stack>
#include <limits.h>
#include <queue>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>
#include <deque>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#include <fstream>
#define REP(i,N)for(long long i=0;i<(N);i++)
#define FOR(i,a,b)for(long long i=(a);i<=(b);i++)
#define FORD(i,a,b)for(long long i=a;i>=(b);i--)
#define ll long long
#define vi vector<ll>
#define vii vector<pair<ll,ll> >
#define vvi vector<vector<ll> >
#define vb vector<bool>
#define pii pair<ll,ll>
#define ALL(x) (x).begin(), (x).end()
#define SZ(a)((ll)(a).size())
#define CHECK_BIT(n,x)((bool)((n)&(((ll)1)<<(x))))
#define pow2(x) ((x)*(x))
#define VELA 2000000009999999999ll
#define X first
#define Y second
#define DBG(x) //cerr<<#x<<" = "<<x<<"\n";
using namespace std;

struct Fenwick{
	vi tree;
	ll f(ll x) { return (x&(-x)); }
	Fenwick(ll n) { tree = vi(n+5,0ll); }
	void Add(ll k, ll val) {
		k++;
		for (;k <SZ(tree);k += f(k))tree[k] += val;
	}
	ll Get(ll k) {
		k++;
		ll res = 0;
		for (;k >0;k -= f(k))res += tree[k];
		return res;
	}
	ll Get(ll a, ll b) {
		return Get(b) - Get(a - 1);
	}
};

vvi graf;
vi color;
vi shots;
set<ll>* DFS(ll v) {
	set<ll>* curr=NULL;
	REP(i, SZ(graf[v])) {
		if (i == 0)
			curr = DFS(graf[v][i]);
		else {
			set<ll>* tmp=DFS(graf[v][i]);
			if (SZ(*tmp) > SZ(*curr))swap(curr, tmp);
			for (auto it = tmp->begin();it != tmp->end();it++)
				curr->insert(*it);
		}
	}
	if (SZ(graf[v])==0) {
		curr = new set<ll>();
		if(color[v]!=-1)
			curr->insert(color[v]);
	}
	shots[v] = SZ(*curr);
	return curr;
}

int main() {
	cin.sync_with_stdio(0);
	ll n, m;
	cin >> n >> m;
	vi ycords;
	vector<pair<pii, pii>> events;
	REP(i, n) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		ycords.push_back(y1);
		ycords.push_back(y2);
		events.push_back({ {x1,i+1000000},{y1,-y2} });
		events.push_back({ {x2 + 1,i},{y1,-y2} });
	}
	color = vi(m+n,-1);
	REP(i, m) {
		ll x, y, k;
		cin >> x >> y >> k;
		ycords.push_back(y);
		color[i+n] = k;
		events.push_back({ {x + 1,i + n},{y,-y} });
	}
	sort(ALL(events));

	sort(ALL(ycords));
	ll nYcords = 0;
	map<ll, ll> renamed;
	REP(i, SZ(ycords)) {
		if (i > 0 && ycords[i] != ycords[i - 1])nYcords++;
		renamed[ycords[i]] = nYcords + 1;
	}

	Fenwick is(SZ(renamed) + 5);
	vector<bool> was(n + m, false);
	vi kill_val(n + m, 0);
	graf=vvi(n + m);
	vector<bool> is_root(n,true);
	REP(i, SZ(events)) {
		ll y1 = renamed[events[i].Y.X], y2 = renamed[-events[i].Y.Y];
		ll typ = events[i].X.Y%1000000;
		if (i == 71)
			DBG("");
		if (was[typ]) {
			is.Add(y1, -kill_val[typ]);
			is.Add(y2 + 1, kill_val[typ]);
		}
		else {
			ll lst = is.Get(y2);
			lst--;
			if (lst != -1) {
				graf[lst].push_back(typ);
				if (typ < n)is_root[typ] = false;
			}
			if (typ < n) {//just rects
				kill_val[typ] = (typ)-(lst);
				is.Add(y1, kill_val[typ]);
				is.Add(y2 + 1, -kill_val[typ]);
			}
			DBG(lst);
		}
		was[typ] = true;
	}
	shots = vi(n + m,-1);
	REP(i,n) {
		if (is_root[i])
			DFS(i);
	}
	REP(i, n) {
		cout << shots[i] << "\n";
	}
	return 0;
}

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