Submission #61222

#	Time	Username	Problem	Language	Result	Execution time	Memory
61222		istlemin	Boat (APIO16_boat)	C++14	31 / 100	1947 ms	125100 KiB

boat

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll mod = 1e9+7;

class Node {
public:
    ll val = 0;
    ll dn,up;
    Node *left;
    Node *right;
    bool children = false;

    Node(ll _dn, ll _up){
        dn = _dn;
        up = _up;
    }

    void ensure(){
        if(dn+1==up) return;
        if(!children){
			children = true;
			left = new Node(dn,(dn+up)/2);
			right = new Node((dn+up)/2,up);
		}
    }

    ll update(ll pos, ll v){
        if(pos<dn||pos>=up) return val;
        if(dn+1==up) return val = (val+v)%mod;
        ensure();
        ll l = left->update(pos,v);
        ll r = right->update(pos,v);
        return val = (l+r)%mod;
    }

    ll query(ll a, ll b){
        if(b<=dn||a>=up) return 0;
        if(a<=dn&&b>=up) return val;
        ensure();
        return (left->query(a,b)+right->query(a,b))%mod;
    }
};

int main(){
	cin.sync_with_stdio(false);
	ll n;
    cin>>n;
    vi a,b;
    a.resize(n);
    b.resize(n);
    //posLastStart.resize(n);
    //posLast.push_back(-1);
    rep(i,0,n) {
		cin>>a[i]>>b[i];
		//posLastStart[i] = posLast.size();
		//rep(j,a[i],b[i]+1) posLast.push_back(j);
	}

	//mem.resize(posLastStart.size()+1,vi(n+1,-1));
    //cout<<(getNum(0,0)+mod-1)%mod<<endl;


    Node dp(0,1e10);

    dp.update(0,1);

    ll ans = 0;

    rep(i,0,n){
		vi u(b[i]+1-a[i]);
		rep(j,a[i],b[i]+1) {
			ans =  (ans + (u[j-a[i]] = dp.query(0,j)))%mod;
		}
		rep(j,a[i],b[i]+1) {
			dp.update(j,u[j-a[i]]);
		}
    }

    cout<<ans<<endl;
    _Exit(0);
}

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