oj.uz

Submission #515620

# Submission time Handle Problem Language Result Execution time Memory
515620 2022-01-19T10:51:07 Z Aldas25 Boat (APIO16_boat) C++14
0 / 100
 2000 ms 469380 KB 
#include<bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(i, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;

const int MAXN = 500;
const ll INF = 1e18;
const ll MOD = 1e9+7;

struct segtree {
    struct node {
        node * le;
        node * ri;
        ll fr, to;
        ll sum = 0;

        node (ll _fr, ll _to) {
            sum = 0;
            le = nullptr;
            ri = nullptr;
            fr = _fr;
            to = _to;
        }

        void upd () {
            ll m = (fr+to)/2;
            if (!le) le = new node (fr, m);
            if (!ri) ri = new node (m+1, to);
        }
    };

    void add (ll p, ll x, node * cur) {
        if ((cur->fr) == (cur->to)) {
            (cur->sum) += x;
            return;
        }

        cur->upd();

        ll m = ((cur->fr) + (cur->to)) / 2;

        if (p <= m)
            add (p, x, cur->le);
        else
            add (p, x, cur->ri);

        (cur->sum) = (cur->le->sum) + (cur->ri->sum);
    }

    ll getSum (ll x, ll y, node * cur) {
        ll fr = (cur->fr);
        ll to = (cur->to);

        if (x > to || y < fr) return 0;
        if (x <= fr && to <= y) return (cur->sum);

        cur->upd();

        return getSum(x, y, cur->le) + getSum(x, y, cur->ri);
    }

    node * root = new node (0, 1e9+1);

    void add (ll p, ll x) {
        add (p, x, root);
    }

    ll get (ll p) {
        return getSum(0, p, root);
    }

} tree;

//vector<ll> dp[MAXN];
int n;
ll a[MAXN], b[MAXN];

int main()
{
    FAST_IO;

    cin >> n;
    FOR(i, 1, n) {
        cin >> a[i] >> b[i];
    }

    //dp[0].pb(1);
    tree.add(0, 1);
//    cout << " h" << endl;

    FOR(i, 1, n) {
        for (int j = b[i]; j >= a[i]; j--) {
                //cout << " i = " << i << " j = " << j << endl;
            ll cur = tree.get(j-1);
        //cout << "  a " << endl;
            tree.add(j, cur);
          //  cout << "  b" << endl;
        }
    }

    ll ans = tree.get(1e9);
    ans--;

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 225428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 225428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 469380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 225428 KB Time limit exceeded
2 Halted 0 ms 0 KB -