Submission #810263

#	Time	Username	Problem	Language	Result	Execution time	Memory
810263		thimote75	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	212 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using num   = long long;

const int START = 0;
const int END   = 1;

const num MOD = 1e9 + 7;

struct Event {
    int start, end;

    Event () = default;
    Event (int start, int end) : start(start), end(end) {}
};

struct Time {
    int time, id;

    int type;

    Time (int time, int id, int type) : time(time), id(id), type(type) {}

    bool operator< (const Time &other) {
        return time < other.time;
    }
};

struct UFD {
    idata parents;

    UFD (int size) {
        parents.resize(size);
        iota(parents.begin(), parents.end(), 0);
    }
    int boss (int x) {
        if (parents[x] != x)
            parents[x] = boss(parents[x]);
        return parents[x];
    }
    bool merge (int a, int b) {
        a = boss(a); b = boss(b);
        if (a == b) return false;

        parents[a] = b;
        return true;
    }

    int size () {
        int res = 0;

        for (int i = 0; i < parents.size(); i ++)
            if (i == parents[i])
                res ++;
        
        return res;
    }
};

using vEvent = vector<Event>;
using vTime  = vector<Time>;

vEvent events;
vTime timings;

const int MAXLOG = 23;
num pow2 (int k) {
    num table[MAXLOG];
    table[0] = 2;
    for (int i = 1; i < MAXLOG; i ++) table[i] = (table[i - 1] * table[i - 1]) % MOD;

    num res = 1;
    for (int i = 0; i < MAXLOG; i ++)
        if ((1 << i) & k)
            res = (res * table[i]) % MOD;
    
    return res;
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N; cin >> N;

    events.resize(N);

    for (int i = 0; i < N; i ++) {
        int s, e;
        cin >> s >> e;

        events[i] = Event(s, e);

        timings.push_back( Time(s, i, START) );
        timings.push_back( Time(e, i, END  ) );
    }

    sort(timings.begin(), timings.end());
    reverse(timings.begin(), timings.end());

    UFD ufd(N);

    set<pair<int, int>> start_enabled;

    for (Time &time : timings) {
        int  id      = time.id;
        bool isStart = time.type == START;

        pair<int, int> start_pair = { events[id].start, id };

        if (isStart) {
            if (start_enabled.find(start_pair) != start_enabled.end())
                start_enabled.erase(start_pair);
        } else {
            pair<int, int> search_pair = { events[id].start, -1 };
            auto it = start_enabled.upper_bound(search_pair);
            bool first = true;
            while (it != start_enabled.end()) {
                const auto data = *it;
                int dataId = data.second;
                
                if (!ufd.merge( id, dataId )) {
                    cout << "0\n";
                    return 0;
                }

                if (first) {
                    search_pair = data;
                    first = false;
                } else start_enabled.erase(data);

                it = start_enabled.upper_bound(search_pair);
            }
            
            start_enabled.insert(start_pair);
        }
    }

    cout << pow2(ufd.size()) << endl;
}

Compilation message (stderr)

port_facility.cpp: In member function 'int UFD::size()':
port_facility.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < parents.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~

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