Submission #93957

#	Time	Username	Problem	Language	Result	Execution time	Memory
93957		Alexa2001	Port Facility (JOI17_port_facility)	C++17	78 / 100	6112 ms	710892 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;
char buffer[bs+2];

/// 19:00

int get_value(int tip, int id)
{
    if(tip == 1) return B[id];
        else return -A[id];
}

bool cmp1(int x, int y)
{
    return B[x] < B[y];
}

bool cmp2(int x, int y)
{
    return A[x] > A[y];
}

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

    public:
        int tip;

        void update(int node, int st, int dr, int pos, int what)
        {
            a[node].push_back(what);
            if(st == dr) return;

            if(pos <= mid) update(left_son, st, mid, pos, what);
                else update(right_son, mid+1, dr, pos, what);
        }

        void init(int node, int st, int dr)
        {
            if(tip == 1) sort(a[node].begin(), a[node].end(), cmp1);
                else sort(a[node].begin(), a[node].end(), cmp2);
            if(st == dr) return;

            init(left_son, st, mid);
            init(right_son, mid+1, dr);
        }

        int query(int node, int st, int dr, int L, int R, int val)
        {
            if(L <= st && dr <= R)
            {
                while(a[node].size() && col[a[node].back()]) a[node].pop_back();
                if(a[node].size() && get_value(tip, a[node].back()) > val)
                    return a[node].back();
                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;
        }
} aint1, aint2;

void dfs(int node, int C = 1)
{
    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;

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

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

    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:102: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:116: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:124: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:133: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: 0 / 22