Submission #704532

#	Time	Username	Problem	Language	Result	Execution time	Memory
704532		keta_tsimakuridze	Port Facility (JOI17_port_facility)	C++14	0 / 100	42 ms	94156 KiB

port_facility

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int p[N], c[N];
set<pair<int,int>> s[N][2];
set<pii> S;
void rem(int x) {
    for(int t = 0; t < 2; t++)
    if(s[x][t].size()) S.erase(*s[x][t].begin());
}
void add(int x) {
    for(int t = 0; t < 2; t++)
    if(s[x][t].size()) S.insert(*s[x][t].begin());
}
void merge(int x, int y) {
    if((int)s[p[x]][1].size() + (int)s[p[x]][0].size() < (int)s[p[y]][1].size() + (int)s[p[y]][0].size()) swap(x, y);
    // c[x] ^ 1 --> c[y]
    if(p[x] == p[y]) assert(0);
    int Y = p[y], X = p[x], T = (c[x] == c[y]);
    for(int t = 0; t < 2; t++) {
        while(s[Y][t].size()) {
            pii x = *s[Y][t].begin();
            p[x.s] = X; c[x.s] = t ^ T;
            s[Y][t].erase(x);
            s[X][t ^ T].insert(x);
        }
    }
}
int main() {
    int n;
    cin >> n;
    vector<pair<int,pair<int,int>> > x;
    for(int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        x.push_back({l, {r, i}});
        x.push_back({r, {0, i}});
        s[i][0].insert({r, i});
        p[i] = i;
    }
    sort(x.begin(), x.end());
    vector<int> f(n + 2);
    for(int i = 0; i < x.size(); i++) {
        if(x[i].s.f == 0) {
            int id = x[i].s.s, r = x[i].f;
            rem(p[id]);
            s[p[id]][c[id]].erase({r, id});
            add(p[id]);
            continue;
        }
        int r = x[i].s.f, l = x[i].f, id = x[i].s.s;
        vector<int> v;
        vector<pii> aa;
        while(S.size() && (*S.begin()).f < r) {
            pii x = *S.begin();
            v.push_back(x.s);
            if(f[p[x.s]] == i + 1) {
                cout << 0; assert(0);
                return 0;
            }
            f[p[x.s]] = i + 1;
            S.erase(x);
            aa.push_back(x);
        }
        while(aa.size()) S.insert(aa.back()), aa.pop_back();
        for(int i = 0; i < v.size(); i++) rem(p[v[i]]), merge(v[i], id);
        add(p[id]);
    }
    int ans = 1;
    for(int i = 1; i <= n; i++) if(p[i] == i) ans = ans * 2 % mod;
    cout << ans;
/*

4
1 5

7 12
11 15
4 10
*/

}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
port_facility.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i = 0; i < v.size(); i++) rem(p[v[i]]), merge(v[i], id);
      |                        ~~^~~~~~~~~~
port_facility.cpp:54:27: warning: unused variable 'l' [-Wunused-variable]
   54 |         int r = x[i].s.f, l = x[i].f, id = x[i].s.s;
      |                           ^

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