Submission #994940

#	Time	Username	Problem	Language	Result	Execution time	Memory
994940		jklepec	Port Facility (JOI17_port_facility)	C++11	78 / 100	6043 ms	136928 KiB

port_facility

#include <bits/stdc++.h> 
  
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define pb push_back 
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) 
  
using namespace std; 
  
typedef long long ll; 
typedef pair <int, int> pii; 
  
const int N = 1e6 + 7, ofs = (1 << 20), mod = 1e9 + 7; 
  
int n, E; 
int l[N], r[N], par[N], siz[N], bio[N], col[N]; 
pii t[2*ofs]; 
vector <int> no[N], adj[N]; 
  
void add(int x, int y) { 
    x += ofs; 
    t[x] = {y, y}; 
    while (x /= 2) t[x] = {max(t[2*x].F, t[2*x+1].F), min(t[2*x].S, t[2*x+1].S)}; 
} 
pii get(int x, int a, int b, int lo = 0, int hi = ofs-1) { 
    if (b < lo || hi < a) return {-1, n}; 
    if (a <= lo && hi <= b) return t[x]; 
    int mid = (lo + hi) / 2; 
    pii p1 = get(2*x, a, b, lo, mid), p2 = get(2*x+1, a, b, mid+1, hi); 
    return {max(p1.F, p2.F), min(p1.S, p2.S)}; 
} 
  
int find(int x) {return (x == par[x]) ? x : (par[x] = find(par[x]));} 
void unite(int x, int y) { 
    x = find(x); y = find(y); 
    if (x == y) return; 
    if (siz[x] < siz[y]) swap(x, y); 
    siz[x] += siz[y]; 
    par[y] = x; 
    for (auto z : no[y]) { 
        add(r[z], x); 
        no[x].pb(z); 
    } 
} 
  
void dfs(int x) { 
    bio[x] = 1; 
    for (auto y : adj[x]) { 
        if (bio[y]) { 
            if (col[x] == col[y]) E = 1; 
            continue; 
        } 
        col[y] = col[x] ^ 1; 
        dfs(y); 
    } 
} 
  
int madd(int x, int y) {return (x+y < mod) ? (x+y) : (x+y-mod);} 
int mul(int x, int y) {return (ll)x*y%mod;} 
  
int main () { 
    FIO; 
    cin >> n; 
    for (int i = 0; i < 2*ofs; i++) t[i] = {-1, n}; 
      
    vector <pii> v; 
      
    for (int i = 0; i < n; i++) { 
        cin >> l[i] >> r[i]; l[i]--; r[i]--; 
        par[i] = i; 
        siz[i] = 1; 
        v.pb({l[i], i}); 
        no[i] = {i}; 
    } 
    sort(all(v)); 
      
    vector <pii> ed; 
      
    for (int i = 0; i < n; i++) { 
        int x = v[i].S; 
        pii o = get(1, l[x], r[x]); 
        if (o.F != -1 && o.F != o.S) { 
            while (o.F != o.S) { 
                unite(o.F, o.S); 
                o = get(1, l[x], r[x]); 
            } 
        } 
        if (o.F != -1) { 
            ed.pb({o.F, x}); 
        } 
        add(r[x], x); 
    } 
      
    for (int i = 0; i < ed.size(); i++) { 
        int x = find(ed[i].F), y = find(ed[i].S); 
        adj[x].pb(y); 
        adj[y].pb(x); 
    } 
      
    int res = 1; 
    for (int i = 0; i < n; i++) { 
        int x = find(i); 
        if (bio[x]) continue; 
        res = mul(res, 2); 
        dfs(x); 
    } 
      
    cout << ((E) ? 0 : res); 
  
    return 0; 
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < ed.size(); i++) {
      |                     ~~^~~~~~~~~~~

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