Submission #843977

#	Time	Username	Problem	Language	Result	Execution time	Memory
843977		raphaelp	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	348 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & (-S))

class FenwickTree
{
private:
    vector<int> ft, ft2;

public:
    FenwickTree(int x)
    {
        ft.assign(x + 1, 0);
        ft2.assign(x + 1, 0);
    }
    int rsq(int j)
    {
        int sum = 0;
        for (; j; j -= LSOne(j))
        {
            sum += ft[j];
            reset(j);
        }
        return sum;
    }
    int rsq2(int j)
    {
        int sum = 0;
        for (; j; j -= LSOne(j))
        {
            sum += ft2[j];
        }
        return sum;
    }
    int rsq(int i, int j) { return rsq(j) - rsq(i - 1); }
    int rsq2(int i, int j) { return rsq2(j) - rsq2(i - 1); }
    void update(int i, int v)
    {
        for (; i < (int)ft.size(); i += LSOne(i))
        {
            ft[i] += v;
        }
    }
    void update2(int i, int v)
    {
        for (; i < (int)ft2.size(); i += LSOne(i))
        {
            ft2[i] += v;
        }
    }
    void reset(int x)
    {
        if (ft[x] == 0)
            return;
        if (x % 2 == 1)
            update2(x, ft[x]);
        int re = x - 1;
        int notre = ~re;
        int ctz = __builtin_ctz(notre);
        for (int i = 0; i < ctz; i++, re -= LSOne(re))
            reset(re);
    }
};

int main()
{
    int N;
    cin >> N;
    FenwickTree FT(2 * N);
    FenwickTree Counted(2 * N);
    vector<pair<int, int>> Tab(N);
    vector<int> fin(N);
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        cin >> fin[i];
        Tab[i] = {temp, fin[i]};
    }
    sort(Tab.begin(), Tab.end());
    sort(fin.begin(), fin.end());
    int buff1 = 0, buff2 = 0, pos = 0;
    for (int i = 0; i <= 2 * N; i++)
    {
        if (i == Tab[buff1].first)
        {
            pos++;
            int moinsmoins = FT.rsq2(Tab[buff1].first, Tab[buff1].second);
            int moins = FT.rsq(Tab[buff1].first, Tab[buff1].second);
            if (moinsmoins)
            {
                moins -= moinsmoins;
                moins++;
            }
            FT.update(Tab[buff1].second, 1);
            pos -= moins;
            buff1++;
        }
        if (pos == 0)
            break;
    }
    long long ans = 1;
    for (int i = 0; i < pos; i++)
    {
        ans *= 2;
        ans = ans % 1000000007;
    }
    if (ans == 1)
        cout << 0;
    else
        cout << ans;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:82:20: warning: unused variable 'buff2' [-Wunused-variable]
   82 |     int buff1 = 0, buff2 = 0, pos = 0;
      |                    ^~~~~

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