Submission #57689

#	Time	Username	Problem	Language	Result	Execution time	Memory
57689		spencercompton	Port Facility (JOI17_port_facility)	C++17	100 / 100	3291 ms	239432 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];
	priority_queue<Ed> all[n];
	for(int i = 0; i<n; i++){
		inside[i] = false;
		in[i] = false;
		last[i] = i;
		all[i].push(Ed(i,-en[i],69));
	}

	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;
			pq.pop();
			inside[cur] = false;
			while(all[id[cur]].size()>0 && -all[id[cur]].top().s<li[i].s){
				all[id[cur]].pop();
			}
			if(all[id[cur]].size()>0 && !inside[all[id[cur]].top().id]){
				int to = all[id[cur]].top().id;
				inside[to] = true;
				pq.push(all[id[cur]].top());
			}
		}
		while(pq.size()>0 && -pq.top().s<li[i].e){
			int now = pq.top().id;
			conflict.push_back(now);
			inside[now] = false;
			pq.pop();
			int ca = id[now];
			int cb = id[li[i].id];
			if(ca==cb){
				continue;
			}
			po--;
			bool flip = red[now]==red[li[i].id];
			if(sz[ca]>sz[cb]){
				swap(ca,cb);
			}
			for(int j = 0; j<comp[ca].size(); j++){
				comp[cb].push_back(comp[ca][j]);
				sz[cb]++;
				id[comp[ca][j]] = cb;
				if(flip){
					red[comp[ca][j]] = !red[comp[ca][j]];
				}
			}
			comp[ca].clear();
			while(all[ca].size()>0){
				all[cb].push(all[ca].top());
				all[ca].pop();
			}
		}
		conflict.push_back(li[i].id);
		for(int j = 0; j<conflict.size(); j++){
			int now = conflict[j];
			if(last[now] != id[now]){
				last[now] = id[now];
				all[id[now]].push(Ed(now,-en[now],69));
			}
		}
		inside[li[i].id] = false;
		vector<int> use;
		for(int j = 0; j<conflict.size(); j++){
			int now = conflict[j];
			if(!in[id[now]]){
				in[id[now]] = true;
				use.push_back(id[now]);
			}
		}
		for(int j = 0; j<use.size(); j++){
			int cur = use[j];
			if(all[cur].size()>0 && !inside[all[cur].top().id]){
				pq.push(all[cur].top());
				inside[all[cur].top().id] = true;
			}
			in[cur] = false;
		}
	}


















	// for(int i = 0; i<li.size(); i++){
	// 	for(int j = 0; j<i; j++){
	// 		if(li[j].e > li[i].s && li[j].e < li[i].e){
	// 			int ca = id[li[i].id];
	// 			int cb = id[li[j].id];
	// 			if(ca==cb){
	// 				continue;
	// 			}
	// 			po--;
	// 			bool flip = red[li[i].id] == red[li[j].id];
	// 			if(sz[ca]>sz[cb]){
	// 				swap(ca,cb);
	// 			}
	// 			//ca into cb
	// 			for(int k = 0; k<comp[ca].size(); k++){
	// 				comp[cb].push_back(comp[ca][k]);
	// 				sz[cb]++;
	// 				if(flip){
	// 					red[comp[ca][k]] = !red[comp[ca][k]];
	// 				}
	// 				id[comp[ca][k]] = cb;
	// 			}
	// 		}
	// 	}
		// 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:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
port_facility.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j<comp[ca].size(); j++){
                   ~^~~~~~~~~~~~~~~~
port_facility.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<conflict.size(); j++){
                  ~^~~~~~~~~~~~~~~~
port_facility.cpp:110:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<conflict.size(); j++){
                  ~^~~~~~~~~~~~~~~~
port_facility.cpp:117:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<use.size(); j++){
                  ~^~~~~~~~~~~
port_facility.cpp:252:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
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: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22