Submission #224496

#	Time	Username	Problem	Language	Result	Execution time	Memory
224496		algorithm16	Plahte (COCI17_plahte)	C++14	0 / 160	2114 ms	524292 KiB

plahte

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<algorithm>
using namespace std;
vector <pair<pair<int,int>,pair<int,int> > > v,v4;
vector <int> v2,v3[80005];
set <int> t[525005],p[525005];
//vector <pair<int,int> > v1[160005];
vector <int> v5;
int off=1,parent[160005],cnt1[80005];
map <pair<int,int>,int> m1;
map <int,vector<pair<int,int> > > v1;
set <int> dfs(int x) {
	//cout << x << "\n";
	set <int> ret,s;
	if(v[x].second.first==-1) {
		ret.insert(m1[v[x].first]);
		return ret;
	}
	for(int i=0;i<v3[x].size();i++) {
		s=dfs(v3[x][i]);
		if(ret.size()<s.size()) swap(ret,s);
		for(set <int>::iterator it=s.begin();it!=s.end();it++) {
			ret.insert(*it);
		}
	}
	cnt1[x]=ret.size();
	return ret;
} 
void send(int x) {
	if(p[x].size()==0) return;
	for(set <int>::iterator it=p[x].begin();it!=p[x].end();it++) {
		if((*it)>0) t[x].insert((*it));
		else t[x].erase(-(*it));
	}
	if(x<off) {
		for(set <int>::iterator it=p[x].begin();it!=p[x].end();it++) {
			p[x*2].insert((*it));
			p[x*2+1].insert((*it));
		}
	}
	p[x].clear();
}
void update(int x,int lo,int hi,int l,int r,int v) {
	if(lo>r or hi<l) return;
	if(lo>=l && hi<=r) {
		p[x].insert(v);
		send(x);
		return;
	}
	update(x*2,lo,(lo+hi)/2,l,r,v);
	update(x*2+1,(lo+hi)/2+1,hi,l,r,v);
}
int query(int x,int lo,int hi,int l,int r) {
	send(x);
	if(lo>r or hi<l) return -1;
	if(lo>=l && hi<=r) {
		if(!t[x].empty()) {
			set <int>::iterator it=t[x].end();
			it--;
			return (*it);
		}
		return -1;
	}
	return max(query(x*2,lo,(lo+hi)/2,l,r),query(x*2+1,(lo+hi)/2+1,hi,l,r));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,ind=0,cnt=0;
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		v2.push_back(x1);
		v2.push_back(x2);
		v2.push_back(y1);
		v2.push_back(y2);
		v.push_back(make_pair(make_pair(x1,y1),make_pair(x2,y2)));
	}
	for(int i=0;i<m;i++) {
		int x,y,c;
		cin >> x >> y >> c;
		m1[make_pair(x,y)]=c;
		v2.push_back(x);
		v2.push_back(y);
		v.push_back(make_pair(make_pair(x,y),make_pair(-1,-1)));
	}
	while(off<2*n+m) off*=2;
	sort(v2.begin(),v2.end());
	v2.erase(unique(v2.begin(),v2.end()),v2.end());
	for(int i=0;i<n+m;i++) {
		int a=0;
		if(v[i].second.first==-1) a=m1[v[i].first];
		v[i].first.first=lower_bound(v2.begin(),v2.end(),v[i].first.first)-v2.begin()+1;
		v[i].first.second=lower_bound(v2.begin(),v2.end(),v[i].first.second)-v2.begin()+1;
		if(a) m1[v[i].first]=a;
		if(v[i].second.first!=-1) {
			v[i].second.first=lower_bound(v2.begin(),v2.end(),v[i].second.first)-v2.begin()+1;
			v1[v[i].second.first+1].push_back(make_pair(v[i].first.second,v[i].second.second));
		}
		if(v[i].second.second!=-1) v[i].second.second=lower_bound(v2.begin(),v2.end(),v[i].second.second)-v2.begin()+1;
	}
	v4=v;
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	/*cout << "\n";
	for(int i=0;i<v.size();i++) {
		cout << v[i].first.first << " " << v[i].first.second << " " << v[i].second.first << " " << v[i].second.second << "\n";
	}
	cout << "abc\n";*/
	for(int i=1;i<=v2.size();i++) {
		//cout << int(t[10].size()) << "\n";
		for(int j=0;j<v1[i].size();j++) {
			update(1,0,off-1,v1[i][j].first,v1[i][j].second,-1);
		}
		v5.clear();
		//cout << "def\n";
		while(ind<v.size() && v[ind].first.first==i) {
			//cout << int(t[10].size()) << "\n";
			if(v[ind].second.first==-1) {
				v5.push_back(ind);
				/*parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].first.second);
				v3[query(1,0,off-1,v[ind].first.second,v[ind].first.second)-1].push_back(ind);*/
			}
			else {
				//if(ind==5) cout << v[ind].first.second << " " << v[ind].second.second << "\n"; 
				parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].second.second);
				if(parent[ind]>0) v3[parent[ind]-1].push_back(ind);
				//cout << int(t[10].size()) << "\n";
				update(1,0,off-1,v[ind].first.second,v[ind].second.second,ind+1);
			}
			ind+=1;
		}
		for(int j=0;j<v5.size();j++) {
			int ind1=v5[j];
			parent[ind1]=query(1,0,off-1,v[ind1].first.second,v[ind1].first.second);
			if(parent[ind1]>0) v3[parent[ind1]-1].push_back(ind1);
		}
	}
	/*for(int i=0;i<v.size();i++) {
		cout << parent[i] << "\n";
	}
	cout << "\n";*/
	for(int i=0;i<v.size();i++) {
		if(parent[i]==-1) dfs(i);
	}
	for(int i=0;i<n;i++) {
		cout << cnt1[int(lower_bound(v.begin(),v.end(),v4[i])-v.begin())] << "\n";
		//cout << "abc\n";
	}
	//assert(0);
	//cout << "123\n";
	/*for(int i=0;i<v.size();i++) {
		cout << parent[i] << " ";
	}*/
	return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'std::set<int> dfs(int)':
plahte.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v3[x].size();i++) {
              ~^~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=v2.size();i++) {
              ~^~~~~~~~~~~
plahte.cpp:119:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v1[i].size();j++) {
               ~^~~~~~~~~~~~~
plahte.cpp:124:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<v.size() && v[ind].first.first==i) {
         ~~~^~~~~~~~~
plahte.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v5.size();j++) {
               ~^~~~~~~~~~
plahte.cpp:150:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++) {
              ~^~~~~~~~~
plahte.cpp:75:16: warning: unused variable 'cnt' [-Wunused-variable]
  int n,m,ind=0,cnt=0;
                ^~~

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