Submission #947277

#	Time	Username	Problem	Language	Result	Execution time	Memory
947277		NValchanov	Boat (APIO16_boat)	C++17	31 / 100	1916 ms	524288 KiB

boat

#include<bits/stdc++.h>

#define endl '\n'
#define a first
#define b second

using namespace std;

typedef long long ll;

const int MAXN = 500 + 10;
const int MAXA = 1e6 + 10;
const int MOD = 1e9 + 7;

int n,cnt;
int a[MAXN];
int b[MAXN];
int dp[MAXA];
int pref[MAXA];
unordered_map <int,int> pos;

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
    }
    a[0] = b[0] = -1;
}

void fill_pos()
{
    vector <int> v;
    set <int> st;

    for(int i = 1; i <= n; i++)
    {
        int from = a[i];
        int to = b[i];

        for(int j = from; j <= to; j++)
        {
            v.push_back(j);
        }
    }
    sort(v.begin(), v.end());

    ll last = -1;

    for(int cur : v)
    {
        if(cur == last)
            continue;

        pos[cur] = ++cnt;
        last = cur;
    }
    ///cout << endl << endl;
    /**
    for(auto x : pos)
    {
        cout << x.first << " " << x.second << endl;
    }
    */
}

void fill_dp()
{
    for(int i = 1; i <= n; i++)
    {
        int from = pos[a[i]];
        int to = pos[b[i]];
        for(int j = to; j >= from; j--)
        {
            dp[j] = (dp[j] + pref[j - 1] + 1 /** za nulata **/) % MOD;
        }
        for(int j = from; j <= cnt; j++)
        {
            pref[j] = (pref[j - 1] + dp[j]) % MOD;
        }
    }
}

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

    read();
    fill_pos();
    fill_dp();

    cout << pref[cnt] << endl;

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42