Submission #93958

#	Time	Username	Problem	Language	Result	Execution time	Memory
93958		Alexa2001	Port Facility (JOI17_port_facility)	C++17	100 / 100	3183 ms	204732 KiB

port_facility

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

typedef pair<int,int> Pair;
const int Nmax = 2e6 + 5, Mod = 1e9 + 7, bs = (1<<17);

int col[Nmax], A[Nmax], B[Nmax];
int n, cursor, who[Nmax];
char buffer[bs+2];

/// 19:00

class STree
{
    int a[Nmax<<2];

    public:
        int tip;

        int query(int node, int st, int dr, int L, int R, int val)
        {
            if(L <= st && dr <= R)
            {
                if(a[node] > val)
                {
                    if(a[node] > 0) return who[a[node]];
                        else return who[-a[node]];
                }
                return -1;
            }

            int res = -1;
            if(L <= mid) res = query(left_son, st, mid, L, R, val);
            if(res == -1 && mid < R) res = query(right_son, mid+1, dr, L, R, val);
            return res;
        }

        void del(int node, int st, int dr, int pos)
        {
            if(st == dr)
            {
                a[node] = INT_MIN;
                return;
            }
            if(pos <= mid) del(left_son, st, mid, pos);
                else del(right_son, mid+1, dr, pos);
            a[node] = max(a[left_son], a[right_son]);
        }

        void init(int node, int st, int dr)
        {
            a[node] = INT_MIN;
            if(st == dr) return;
            init(left_son, st, mid);
            init(right_son, mid+1, dr);
        }

        void update(int node, int st, int dr, int pos, int val)
        {
            if(st == dr)
            {
                a[node] = val;
                return;
            }
            if(pos <= mid) update(left_son, st, mid, pos, val);
                else update(right_son, mid+1, dr, pos, val);
            a[node] = max(a[left_son], a[right_son]);
        }

} aint1, aint2;

void dfs(int node, int C = 1)
{
    aint1.del(1, 1, 2*n, A[node]);
    aint2.del(1, 1, 2*n, B[node]);
    col[node] = C;

    while(1)
    {
        int x = aint1.query(1, 1, 2*n, A[node], B[node], B[node]);
        if(x == -1) break;
        dfs(x, 3 - C);
    }

    while(1)
    {
        int x = aint2.query(1, 1, 2*n, A[node], B[node], -A[node]);
        if(x == -1) break;
        dfs(x, 3 - C);
    }
}

bool check(vector<Pair> &v)
{
    sort(v.begin(), v.end());

    priority_queue< int, vector<int>, greater<int> > heap;
    int i;

    for(i=0; i<v.size(); ++i)
    {
        while(heap.size() && heap.top() < v[i].first) heap.pop();
        if(heap.size() && heap.top() < v[i].second) return 0;
        heap.push(v[i].second);
    }
    return 1;
}

void read(int &n)
{
    while(!isdigit(buffer[cursor]))
    {
        ++cursor;
        if(cursor == bs) fread(buffer, 1, bs, stdin), cursor = 0;
    }

    n = 0;
    while(isdigit(buffer[cursor]))
    {
        n = n * 10 + buffer[cursor] - '0';
        ++cursor;
        if(cursor == bs) fread(buffer, 1, bs, stdin), cursor = 0;
    }
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    fread(buffer, 1, bs, stdin), cursor = 0;

    int i;
    read(n);
    for(i=1; i<=n; ++i) read(A[i]), read(B[i]);

    aint1.tip = 1; aint2.tip = 2;

    aint1.init(1, 1, 2*n);
    aint2.init(1, 1, 2*n);

    for(i=1; i<=n; ++i)
    {
        aint1.update(1, 1, 2*n, A[i], B[i]);
        aint2.update(1, 1, 2*n, B[i], -A[i]);

        who[A[i]] = who[B[i]] = i;
    }

    int ans = 1;
    for(i=1; i<=n; ++i)
        if(!col[i])
        {
            ans = 2 * ans % Mod;
            dfs(i);
        }

    vector<Pair> v[3];
    for(i=1; i<=n; ++i) v[col[i]].push_back({A[i], B[i]});

    if(check(v[1]) && check(v[2])) cout << ans << '\n';
        else cout << 0 << '\n';

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool check(std::vector<std::pair<int, int> >&)':
port_facility.cpp:104:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~
port_facility.cpp: In function 'void read(int&)':
port_facility.cpp:118:53: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         if(cursor == bs) fread(buffer, 1, bs, stdin), cursor = 0;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
port_facility.cpp:126:53: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         if(cursor == bs) fread(buffer, 1, bs, stdin), cursor = 0;
                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:135:32: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread(buffer, 1, bs, stdin), cursor = 0;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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