Submission #57665

#	Time	Username	Problem	Language	Result	Execution time	Memory
57665		spencercompton	Port Facility (JOI17_port_facility)	C++17	10 / 100	29 ms	24368 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> comp[1000000];
vector<int> sz;
vector<int> id;
vector<bool> red;
class Ed{
	public:
		int id, s, e;
		Ed(int a, int b, int c){
			id = a;
			s = b;
			e = c;
		}
		bool operator<(const Ed &o) const{
			return s<o.s;
		}
};
vector<Ed> li;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll mod = 1000000007LL;
	int n;
	cin >> n;
	int st[n];
	int en[n];
	for(int i = 0; i<n; i++){
		red.push_back(true);
		id.push_back(i);
		sz.push_back(1);
		comp[i].push_back(i);
		int a, b;
		cin >> a >> b;
		st[i] = a;
		en[i] = b;
		li.push_back(Ed(i,a,b));
	}
	sort(li.begin(),li.end());
	priority_queue<Ed> pq; 
	int po = n;
	bool in[n];
	//talking about components
	bool inside[n];
	//talking about elements
	int last[n];
	for(int i = 0; i<n; i++){
		inside[i] = false;
		in[i] = false;
		last[i] = -1;
	}
	priority_queue<Ed> all[n];
	for(int i = 0; i<li.size(); i++){
		vector<int> conflict;
		while(pq.size()>0 && -pq.top().s <li[i].s){
			int cur = pq.top().id;
			inside[cur] = false;
			pq.pop();
			while(all[id[cur]].size()>0 && -all[id[cur]].top().s<li[i].s){
				inside[all[id[cur]].top().id] = false;
				all[id[cur]].pop();
			}
			if(all[id[cur]].size()>0 && !inside[all[id[cur]].top().id]){
				Ed ee = all[id[cur]].top();
				pq.push(Ed(ee.id, ee.s,6969));
				inside[ee.id] = true;
			}
		}
		while(pq.size()>0 && -pq.top().s <li[i].e){
			int cur = pq.top().id;
			conflict.push_back(cur);

			inside[cur] = false;
			int ca = id[li[i].id];
			int cb = id[cur];

			
			pq.pop();
			if(ca==cb){
				continue;
			}
			po--;
			bool flip = red[li[i].id] == red[cur];
			if(sz[ca]>sz[cb]){
				swap(ca,cb);
			}
			//ca into cb
			for(int j = 0; j<comp[ca].size(); j++){
				comp[cb].push_back(comp[ca][j]);
				sz[cb]++;
				if(flip){
					red[comp[ca][j]] = !red[comp[ca][j]];
				}
				id[comp[ca][j]] = cb;
			}
			comp[ca].clear();
			while(all[ca].size()>0){
				all[ca].pop();
			}
		}
		conflict.push_back(li[i].id);
		inside[li[i].id] = false;
		vector<int> use;
		for(int j = 0; j<conflict.size(); j++){
			if(!in[id[conflict[j]]]){
				use.push_back(id[conflict[j]]);
				in[id[conflict[j]]] = true;
			}
			if(last[conflict[j]] != id[conflict[j]]){
				all[id[conflict[j]]].push(Ed(conflict[j],-en[conflict[j]],696969));
				last[conflict[j]] = id[conflict[j]];
			}
		}
		for(int j = 0; j<use.size(); j++){
			int cur = use[j];
			if(all[cur].size()>0 && !inside[all[cur].top().id]){
				inside[all[cur].top().id] = true;
				pq.push(all[cur].top());
			}
			in[cur] = false;
		}
	}
	ll ans = 1LL;
	for(int i = 0; i<po; i++){
		ans *= 2LL;
		ans %= mod;
	}
	bool ok = true;
	priority_queue<int> reds;
	priority_queue<int> blues;
	for(int i = 0; i<n; i++){
		for(int j = i+1; j<n; j++){
			if(li[i].e > li[j].s && li[i].e < li[j].e && red[li[i].id] == red[li[j].id]){
				ok = false;
			}
		}
	}
	// for(int i = 0; i<li.size(); i++){
	// 	while(reds.size()>0 && -reds.top() < li[i].s){
	// 		reds.pop();
	// 	}
	// 	while(blues.size()>0 && -blues.top() < li[i].s){
	// 		blues.pop();
	// 	}
	// 	if(!red[li[i].id]){
	// 		if(blues.size()>0 && -blues.top()<li[i].e){
	// 			ok = false;
	// 		}
	// 		blues.push(-li[i].e);
	// 	}
	// 	else{
	// 		if(reds.size()>0 && -reds.top() < li[i].e){
	// 			ok = false;
	// 		}
	// 		reds.push(-li[i].e);
	// 	}
	// }
	if(!ok){
		ans = 0LL;
	}
	assert(ans>=0);
	cout << ans << endl;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
port_facility.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j<comp[ca].size(); j++){
                   ~^~~~~~~~~~~~~~~~
port_facility.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<conflict.size(); j++){
                  ~^~~~~~~~~~~~~~~~
port_facility.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<use.size(); j++){
                  ~^~~~~~~~~~~
port_facility.cpp:27:6: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  int st[n];
      ^~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22