Submission #162204

#	Time	Username	Problem	Language	Result	Execution time	Memory
162204		DifferentHeaven	Plahte (COCI17_plahte)	C++17	160 / 160	1149 ms	74708 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 = 1e5 + 7;

int m, n, gx, gy, tot, t;
int p[N], res[N], cnt[N], st[N], ft[N], ver[N], deg[N];
vector <int> col[N];
bool vis[N];
vector <int> vx, vy;
map <int, int> mx, my;
vector <int> adj[N];
int sz[N];

void getsz(int v, int p){
    sz[v] = 1;
    st[v] = ++t;
    ver[t] = v;  
    for(auto u : adj[v])
        if(u != p){
            getsz(u, v);
            sz[v] += sz[u];
        }
    ft[v] = t;
}

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[5 * N];

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

	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;
}

inline void add(int c){
	cnt[c]++;
	if (cnt[c] == 1) tot++;
}

inline void del(int c){
	cnt[c]--;
	if (cnt[c] == 0) tot--;
}

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;

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

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

	for (int u: adj[v])
		if (u != p && u != bigChild)
			for (int x = st[u]; x <= ft[u]; x++){
				int vertice = ver[x];
				for (int c: col[vertice])
					add(c);
			}

	for (int c: col[v])
		add(c);
	res[v] = tot;
	
    if(keep == 0){
    	for (int x = st[v]; x <= ft[v]; x++){
    		int vertice = ver[x];
    		for (int c: col[vertice])
    			del(c);
    	}
    }
}

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);
				if (v){
					adj[v].push_back(id);
					deg[id]++;
					p[id] = v;
				}
				IT.Update(1, 1, gy, l, h, id);
			}
			if (id < 0){
				IT.Update(1, 1, gy, l, h, p[-id]);
			}
			if (id > 0 && id > N){
				int v = IT.Query(1, 1, gy, l, h);
				col[v].push_back(id - N);
			}
		}
	}
	t = 0;

	for (int i = 1; i <= n; i++){
		if (deg[i] == 0 && !sz[i])
			getsz(i, i);
	}

	for (int i = 1; i <= n; i++)
		if (deg[i] == 0 && !vis[i]){
			tot = 0;
			dfs(i, -1, 0);
		}

	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:77: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:87: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:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++)
                  ~~^~~~~~~~~~
plahte.cpp: In function 'void dfs(int, int, bool)':
plahte.cpp:122:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(bigChild != -1)
     ^~
plahte.cpp:125:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (int u: adj[v])
  ^~~
plahte.cpp: In function 'int main()':
plahte.cpp:194:7: warning: unused variable 'lx' [-Wunused-variable]
   int lx = rect[i].lx;
       ^~
plahte.cpp:150: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:150:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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