Submission #162200

#	Time	Username	Problem	Language	Result	Execution time	Memory
162200		DifferentHeaven	Plahte (COCI17_plahte)	C++17	0 / 160	2062 ms	110784 KiB

plahte

#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<

using namespace std;

const int N = 2e5 + 7;

int m, n, gx, gy;
int p[N], res[N];
bool vis[N];
vector <int> vx, vy;
map <int, int> mx, my;
vector <int> adj[N];
set <int> Set[N];
int sz[N];

void getsz(int v, int p){
    sz[v] = Set[v].size();  
    for(auto u : adj[v])
        if(u != p){
            getsz(u, v);
            sz[v] += sz[u];
        }
}

struct Rect{
	int lx, ly, hx, hy, id;
	Rect() {}
	Rect(int lx, int ly, int hx, int hy): lx(lx), ly(ly), hx(hx), hy(hy) {}
}rect[N];

struct Shot{
	int x, y, c;
	Shot() {}
	Shot(int x, int y, int c): x(x), y(y), c(c) {}
}shot[N];

struct Event{
	int id, l, h;
	Event() {}
	Event(int id, int l, int h): id(id), l(l), h(h) {}
};
vector <Event> event[N];

struct segTree{
	int tree[N << 3];
	int lazy[N << 3];

	segTree(){
		memset(lazy, -1, sizeof(lazy));
	}

	void Lazy(int x){
		if (lazy[x] != -1){
			tree[x] = lazy[x];
			lazy[2 * x] = lazy[x];
			lazy[2 * x + 1] = lazy[x];
			lazy[x] = -1;
		}
	}

	void Update(int x, int l, int r, int i, int j, int val){
		Lazy(x);
		if (l > j || r < i) return;
		if (l >= i &&  r <= j) {
			lazy[x] = val;
			Lazy(x);
			return;
		}
		int mid = l + r >> 1;
		Update(2 * x, l, mid, i, j, val);
		Update(2 * x + 1, mid + 1, r, i, j, val);
		tree[x] = max(tree[2 * x], tree[2 * x + 1]);
	}

	int Query(int x, int l, int r, int i, int j){
		Lazy(x);
		if (l > j || r < i)  return 0;
		if (l >= i && r <= j) return tree[x];
		int mid = l + r >> 1;
		return max(Query(2 * x, l, mid, i, j), Query(2 * x + 1, mid + 1, r, i, j));
	}
}IT;

inline void Compress(vector <int> v, map <int, int> &m, int &g){
	sort(v.begin(), v.end());
	m[v[0]] = ++g;
	for (int i = 1; i < v.size(); i++)
		if (v[i] != v[i - 1])
			m[v[i]] = ++g;
}

void dfs(int v, int p, bool keep){
    int mx = -1, bigChild = -1;
    vis[v] = true;

    for(auto u : adj[v])
       if(u != p && sz[u] > mx)
          mx = sz[u], bigChild = u;

    // db(v _ bigChild _ mx);
    for(auto u : adj[v])
        if(u != p && u != bigChild)
            dfs(u, v, 0); 

    if(bigChild != -1)
        dfs(bigChild, v, 1);  

    // db(v _ adj[v].size());
  //   for(auto u : adj[v])
		// if(u != p && u != bigChild){
		// 	for (int x: Set[u]){
		// 		Set[v].insert(x);
		// 	}
		// }
	if (p > 0)
		for (int x: Set[v])
			Set[p].insert(x);
	res[v] = Set[v].size();
    if(keep == 0)
    	Set[v].clear();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);

	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		int lx, ly, hx, hy;
		cin >> lx >> ly >> hx >> hy;
		rect[i].id = i;
		rect[i] = Rect(lx, ly, hx, hy);

		vx.push_back(lx); vx.push_back(hx);
		vy.push_back(ly); vy.push_back(hy);
	}

	for (int i = 1; i <= m; i++){
		int x, y, c;
		cin >> x >> y >> c;
		shot[i] = Shot(x, y, c);

		vx.push_back(x);
		vy.push_back(y);
	}

	Compress(vx, mx, gx);
	Compress(vy, my, gy);


	for (int i = 1; i <= n; i++){
		int lx = mx[rect[i].lx];
		int ly = my[rect[i].ly];
		int hx = mx[rect[i].hx];
		int hy = my[rect[i].hy];

		rect[i] = Rect(lx, ly, hx, hy);
		event[lx].push_back(Event(i, ly, hy));
	}

	for (int i = 1; i <= m; i++){
		int x = mx[shot[i].x];
		int y = my[shot[i].y];
		shot[i].x = x;
		shot[i].y = y;
		event[x].push_back(Event(N + shot[i].c, y, y));
	}

	for (int i = 1; i <= n; i++){
		int lx = rect[i].lx;
		int ly = rect[i].ly;
		int hx = rect[i].hx;
		int hy = rect[i].hy;

		event[hx].push_back(Event(-i, ly, hy));
	}

	for (int i = 1; i <= gx; i++){
		for (Event e: event[i]){
			int id = e.id;
			int l = e.l;
			int h = e.h;

			if (id > 0 && id < N){
				int v = IT.Query(1, 1, gy, l, h);
				// db(id _ v _ l _ h);
				if (v){
					adj[id].push_back(v);
					adj[v].push_back(id);
					p[id] = v;
				}
				IT.Update(1, 1, gy, l, h, id);
			}
			if (id < 0){
				// db(-id _ p[-id] _ l _ h);
				IT.Update(1, 1, gy, l, h, p[-id]);
				// for (int j = 1; j <= gy; j++)
				// 	cerr << IT.Query(1, 1, gy, j, j) << ' ';
				// cerr << endl;
			}
			if (id > 0 && id > N){
				int v = IT.Query(1, 1, gy, l, h);
				// db(v _ l _ h);
				Set[v].insert(id - N);
			}
		}
	}

	// for (int i = 1; i <= n; i++){
	// 	cout << i << " | ";
	// 	for (int x: Set[i])
	// 		cout << x << ' ';
	// 	cout << endl;
	// }

	for (int i = 1; i <= n; i++)
		if (!sz[i])
			getsz(i, -1);

	for (int i = 1; i <= n; i++)
		if (!vis[i])
			dfs(i, -1, 1);

	for (int i = 1; i <= n; i++)
		cout << res[i] << endl;

}

Compilation message (stderr)

plahte.cpp: In member function 'void segTree::Update(int, int, int, int, int, int)':
plahte.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
plahte.cpp: In member function 'int segTree::Query(int, int, int, int, int)':
plahte.cpp:84:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
plahte.cpp: In function 'void Compress(std::vector<int>, std::map<int, int>&, int&)':
plahte.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++)
                  ~~^~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:177:7: warning: unused variable 'lx' [-Wunused-variable]
   int lx = rect[i].lx;
       ^~
plahte.cpp:132:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:132:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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