Submission #373294

#	Time	Username	Problem	Language	Result	Execution time	Memory
373294		8e7	Port Facility (JOI17_port_facility)	C++14	0 / 100	25 ms	24428 KiB

port_facility

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define maxn 1000005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;


struct obj{
	int l, r, id;
	obj() {
		l = 0, r = 0, id = 0;
	}
	obj(int a, int b, int c) {
		l = a, r = b, id = c;
	}
};
obj a[maxn];
int ma[maxn];
inline bool cmp1(obj x, obj y) {
	return x.l < y.l;
}
inline bool cmp2(obj x, obj y) {
	return x.r > y.r;
}

int bit[2 * maxn];
void modify(int ind, int val) {
	for (;ind < 2 * maxn;ind += ind & (-ind)) bit[ind] = max(bit[ind], val);
}
int query(int ind) {
	int ret = 0;
	for (;ind > 0;ind -= ind & (-ind)) ret = max(ret, bit[ind]);
	return ret;
}

vector<set<int> > v;
inline bool sc(int x, int y) {
	return *v[x].begin() < *v[y].begin();
}
set<int, decltype(&sc) > se(sc);

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) cin >> a[i].l >> a[i].r, a[i].id = i;
    sort(a, a + n, cmp1);
    int poss = 1;
    for (int i = 0;i < n;i++) {
    	ma[a[i].id] = query(a[i].r);
    	//cout << a[i].l << " " << a[i].r << " " << ma[a[i].id] << endl;
    	modify(a[i].r, a[i].r);
    }
    sort(a, a + n, cmp2);
    for (int i = 0;i < n;i++) {
    	int val = query(2 * maxn - a[i].l);
    	if (2 * maxn - val < ma[a[i].id]) {
    		poss = 0;
    		break;
    	}
    	modify(2 * maxn - a[i].l, 2 * maxn - a[i].l);
    }

    if (poss) {
    	sort(a, a + n, cmp1);
    	ll ans = 1;
    	for (int i = 0;i < n;i++) {
    		while (se.size() && *v[*se.begin()].begin() < a[i].l) {
    			v[*se.begin()].erase(v[*se.begin()].begin());
    			if (v[*se.begin()].size() == 0) {
    				se.erase(se.begin());
    				ans = (ans * 2) % mod;
    			}
    		}
    		vector<int> me;
    		for (int j:se) {
    			if (a[i].r > *v[j].begin()) {
    				me.push_back(j);
    			} else {
    				break;
    			}
    		}
    		if (me.size() == 0) {
    			set<int> add;
    			add.insert(a[i].r);
    			v.push_back(add);
    			se.insert(v.size() - 1);
    		} else {
    			v[*se.begin()].insert(a[i].r);
    			for (int j = 1;j < me.size();j++) {
    				for (int k:v[me[j]]) {
    					v[me[0]].insert(k);
    				}
    				v[me[j]].clear();
    				se.erase(se.find(me[j]));
    			}
    		}
    	}
    	for (int i = 0;i < se.size();i++) ans = ans * 2 % mod;
    	cout << ans << "\n";
    } else {
    	cout << 0 << "\n";
    }

}
/*
4
1 3
2 5
4 8
6 7

3
1 4
2 5
3 6

5
1 4
2 10
6 9
7 8
3 5

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12
 */

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |        for (int j = 1;j < me.size();j++) {
      |                       ~~^~~~~~~~~~~
port_facility.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int, bool (*)(int, int)>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |      for (int i = 0;i < se.size();i++) ans = ans * 2 % mod;
      |                     ~~^~~~~~~~~~~

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