Submission #412505

#	Time	Username	Problem	Language	Result	Execution time	Memory
412505		pure_mem	Plahte (COCI17_plahte)	C++14	0 / 160	215 ms	26664 KiB

plahte

#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define double long double
 
using namespace std;
 
const int N = 1e5 + 12;
            
int n, m;
pair< pair<int, int>, pair<int, int> > p[N];
vector< pair< int, pair<pair<int, int>, int> > > g1;
vector< pair< pair<int, int>, int > > g2;
vector< int > graph[N], clr[N];

int answer[N], was[N], last[N], T, res;

void add(int u){
	for(int v: clr[u]){
		if(last[v] != T) last[v] = T, res++;
	}
}
void rest(){
	T++, res = 0;
}

void inputs(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> p[i].X.X >> p[i].X.Y >> p[i].Y.X >> p[i].Y.Y;
		g1.push_back(MP(p[i].X.X, MP(MP(p[i].X.Y, p[i].Y.Y), -i)));
		g1.push_back(MP(p[i].Y.X, MP(MP(p[i].X.Y, p[i].Y.Y), i)));
	}
	unordered_map<int, int> mp;
	for(int i = 1, x, y, z;i <= m;i++){
		cin >> x >> y >> z; 
		if(!mp[z]) mp[z] = mp.size();
		z = mp[z];
		g2.push_back(MP(MP(x, y), z));	
	}
	sort(g1.begin(), g1.end()), sort(g2.begin(), g2.end());
	set< pair< pair<int, int>, int > > active, active2;
	for(int i = 0, j = 0;i < g1.size() || j < g2.size();){
		if(i < g1.size() && (j == g2.size() || (g1[i].X < g2[j].X.X || (g1[i].X == g2[j].X.X && g1[i].Y.X.X <= g2[j].X.Y)))){
			if(g1[i].Y.Y < 0){
				auto it = active.insert(MP(g1[i].Y.X, -g1[i].Y.Y)).X;
				active2.insert(MP(MP(g1[i].Y.X.Y, g1[i].Y.X.X), -g1[i].Y.Y));
				if(it != active.begin()){
					it--;
					pair<int, int> lm = it->X;
					if(lm.X <= g1[i].Y.X.X && g1[i].Y.X.Y <= lm.Y){
						graph[it->Y].push_back(-g1[i].Y.Y);	
					}
				}
			}
			else{
				if(j < g2.size() && g1[i].X == g2[j].X.X && g1[i].Y.X.Y >= g2[j].X.Y) goto mans;
				active.erase(MP(g1[i].Y.X, g1[i].Y.Y));
				active2.erase(MP(MP(g1[i].Y.X.Y, g1[i].Y.X.X), g1[i].Y.Y));
			}
			i++;
		}
		else{
			mans:
			auto it = active.upper_bound(MP(MP(g2[j].X.Y + 1, -1), -1));
			if(it != active.begin()){
				it--;
				pair<int, int> lm = it->X;
				if(lm.X <= g2[j].X.Y && g2[j].X.Y <= lm.Y){
					clr[it->Y].push_back(g2[j].Y);	
				}
				else{
					it = active2.lower_bound(MP(MP(g2[j].X.Y, -1), -1));
					if(it != active2.end()){
        				pair<int, int> lm = it->X;
        				if(lm.Y <= g2[j].X.Y && g2[j].X.Y <= lm.X){
        					clr[it->Y].push_back(g2[j].Y);	
        				}
        			}	
				}
			}
			j++;
		}
	}
}

int sz[N], tin[N], tout[N], ord[N], timer;

void dfs1(int v){
	timer++;
	ord[timer] = v, tin[v] = timer;
	was[v] = 1, sz[v] = 1;
	for(int to: graph[v]){
		dfs1(to);
		sz[v] += sz[to];
	}
	tout[v] = timer;
}

void dfs2(int v, bool keep){
	int mx = 0;
	for(int to: graph[v]){
		if(sz[mx] < sz[to]) mx = to;
	}		
	for(int to: graph[v]){
		if(to != mx) dfs2(to, 0);
	}
	if(mx) dfs2(mx, 1);
	add(v);
	for(int to: graph[v]){
		if(to != mx){
			for(int i = tin[to];i <= tout[to];i++) add(ord[i]);	
		}
	}
	answer[v] = res;
	if(!keep) rest();
}

void prep(){
	rest();
	for(auto tmp: g1){
		int i = -tmp.Y.Y;
		if(i < 0 || was[i]) continue;
		dfs1(i); dfs2(i, 0);
	}
	for(int i = 1;i <= n;i++) cout << answer[i] << "\n";	
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
	inputs();
	prep();
}

Compilation message (stderr)

plahte.cpp: In function 'void inputs()':
plahte.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0, j = 0;i < g1.size() || j < g2.size();){
      |                       ~~^~~~~~~~~~~
plahte.cpp:46:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 0, j = 0;i < g1.size() || j < g2.size();){
      |                                        ~~^~~~~~~~~~~
plahte.cpp:47:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   if(i < g1.size() && (j == g2.size() || (g1[i].X < g2[j].X.X || (g1[i].X == g2[j].X.X && g1[i].Y.X.X <= g2[j].X.Y)))){
      |      ~~^~~~~~~~~~~
plahte.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   if(i < g1.size() && (j == g2.size() || (g1[i].X < g2[j].X.X || (g1[i].X == g2[j].X.X && g1[i].Y.X.X <= g2[j].X.Y)))){
      |                        ~~^~~~~~~~~~~~
plahte.cpp:60:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     if(j < g2.size() && g1[i].X == g2[j].X.X && g1[i].Y.X.Y >= g2[j].X.Y) goto mans;
      |        ~~^~~~~~~~~~~

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