oj.uz

Submission #638894

# Submission time Handle Problem Language Result Execution time Memory
638894 2022-09-07T21:24:19 Z beedle Plahte (COCI17_plahte) C++17
64 / 160
 751 ms 163860 KB 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define PI 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 5e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

struct seg
{
	int id, x, lowy, upy;
	bool type;	// 0 for open, 1 for close

	bool operator< (const seg &s) const
	{
		if(this->x!=s.x)
		return this->x<s.x;
		else
		return this->lowy<s.lowy;
	}
};

const int MAXN=4*80000+100;
vector <int> cols[MAXN];
vector <int> adj[MAXN];
int parent[MAXN];
bool marked[MAXN];

int t[4*MAXN+40];
 
void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = -1;
    }
}

void push(int v) {
    if (t[v]!=-1) {
        t[v*2] = t[v*2+1] = t[v];
        t[v]=-1;
    }
}
 
void update(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] = new_val;
        
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), new_val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
    }
}
 
int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return t[v];
    }
    push(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) 
        return get(v*2, tl, tm, pos);
    else
        return get(v*2+1, tm+1, tr, pos);
}

set <int> *col_set[MAXN];
int ans[MAXN];

void dfs(int v)
{
	marked[v]=true;
	col_set[v]=new set <int> ();
	for(auto x:cols[v])
	col_set[v]->insert(x);

	for(auto u:adj[v])
	if(!marked[u])
	{
		dfs(u);

		if(sz(*col_set[v])<sz(*col_set[u]))
		{
			for(auto x:*col_set[v])
			col_set[u]->insert(x);
			col_set[v]=col_set[u];
		}
		else
		{
			for(auto x:*col_set[u])
			col_set[v]->insert(x);
		}	
	}	

	ans[v]=sz(*col_set[v]);
}

signed main()
{    
    fast;

    // freopen("hillwalk.in","r",stdin);
    // freopen("hillwalk.out","w",stdout);

	int n,m;
	cin>>n>>m;

	set <int> n_s;

	int x1[n+1],y1[n+1],x2[n+1],y2[n+1];
	rep(i,1,n)
	{
		cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
		n_s.insert(x1[i]);
		n_s.insert(x2[i]);
		n_s.insert(y1[i]);
		n_s.insert(y2[i]);
	}

	int bx[m+1],by[m+1],bcol[m+1];
	rep(i,1,m)
	{
		cin>>bx[i]>>by[i]>>bcol[i];
		n_s.insert(bx[i]);
		n_s.insert(by[i]);
	}

	int cnt=2;
	map <int,int> n_m;
	for(auto x:n_s)
	n_m[x]=cnt, cnt+=2;

	int mx=cnt+100;

	seg s[2*n+1];
	rep(i,1,n)
	{
		s[i]={int(i),n_m[x1[i]],n_m[y1[i]],n_m[y2[i]],0};
		s[i+n]={int(i),n_m[x2[i]],n_m[y1[i]],n_m[y2[i]],1};
	}

	// rep(i,1,2*n)
	// cout<<s[i].id<<" "<<s[i].x<<" "<<s[i].lowy<<" "<<s[i].upy<<" "<<s[i].type<<endl;

	sort(s+1,s+2*n+1);
	
	pair <int,int> pts[m+1];
	rep(i,1,m)
	pts[i]={n_m[bx[i]],n_m[by[i]]};

	map <pair<int,int>,int> col_mp;
	rep(i,1,m)
	col_mp[pts[i]]=bcol[i];

	sort(pts+1,pts+m+1);

	int thr[mx];
	fill(thr,thr+mx,0);
	build(thr,1,0,mx-1);

	int pidx=1;

	rep(i,1,2*n)
	{
		while(pidx<=m && (s[i].type?(pts[pidx].ff<=s[i].x):(pts[pidx].ff<s[i].x)))
		{
			int vertex=get(1,0,mx-1,pts[pidx].ss);
			cols[vertex].pb(col_mp[pts[pidx]]);
			pidx++;
			// cout<<"HERE : "<<vertex<<endl;
		}

		int par=get(1,0,mx-1,s[i].upy+1);

		if(!s[i].type)
		{
			if(par!=0)
			{
				adj[s[i].id].pb(par);
				adj[par].pb(s[i].id);
				parent[s[i].id]=par;
			}
			update(1,0,mx-1,s[i].lowy,s[i].upy,s[i].id);
		}
		else
		{
			update(1,0,mx-1,s[i].lowy,s[i].upy,par);
		}
	}

	// rep(i,1,n)
	// {
	// 	cout<<i<<" : "<<endl;
	// 	for(auto x:adj[i])
	// 	cout<<x<<" ";
	// 	cout<<endl;
	// 	for(auto x:cols[i])
	// 	cout<<x<<" ";
	// 	cout<<endl;
	// }

	rep(i,1,n)
	if(!marked[i])
	{
		int curr=i;
		while(parent[curr]!=0)
		curr=parent[curr];

		dfs(curr);
	}

	rep(i,1,n)
	cout<<ans[i]<<endl;

    return 0;
}

/*
2​ ​2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
*/

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 44204 KB Output is correct
2 Correct 194 ms 44512 KB Output is correct
3 Correct 8 ms 15304 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 49820 KB Output is correct
2 Correct 252 ms 48332 KB Output is correct
3 Correct 8 ms 15364 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 403 ms 120780 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 723 ms 162512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 751 ms 163860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -