Submission #124344

#	Time	Username	Problem	Language	Result	Execution time	Memory
124344		Mtaylor	Boat (APIO16_boat)	C++17	9 / 100	2063 ms	223452 KiB

boat

#include <bits/stdc++.h>
 
    using namespace std;
    typedef long long ll;
    typedef vector<ll> vl ;
 
    #define mp make_pair
    #define pb push_back
    #define f first
    #define s second
    #define all(v) (v).begin(),(v).end()
 
 
    const int MOD = 1000000007;
    const int N = 1000005;
    const double PI =4*atan(1);
    const double eps = 1e-7;
    
    ll n;
    map<ll,ll> maa;
    map<ll,ll> mal;
    set<ll> ss;
    ll a[N];
    ll b[N];
    ll c[N];
    ll d[N];
    ll tree[N];
    ll tree2[N];
 
    void update(ll x, ll val){
        for(;x<=3000;x+=(x)&(-x)){
            tree[x]+=val;
            tree[x]%=MOD;
        }
    }
 
    ll get(ll x){
        ll to_return =0;
        for(;x>0;x-=x&(-x)){
            to_return +=tree[x];
            to_return %=MOD;
        }
        return to_return;
    }
 
 
    int main(){
        ios::sync_with_stdio(0);
        //freopen("easy.txt","r",stdin);
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> a[i];
            cin >> b[i];
            for(int j=a[i];j<=b[i];j++){
            	ss.insert(j);
            }
        }
        ll cnt=2;
        for(auto t:ss){
            mal[t]=cnt;
            maa[cnt]=t;
            cnt++;
        }
        update(1,1);
        ll ans=0;
        for(int i=0;i<n;i++){
            for(int j=mal[a[i]];j<=mal[b[i]];j++){
            	if(j==mal[a[i]])
                	ans+=get(j);
                else{
                	ans+=((maa[j]-maa[j-1])%MOD) * (get(j-1)+tree2[j-1])%MOD;
                }
                //cout << i << " " << maa[j] << " " << ans << endl;
                ans%=MOD;
            }
            for(int j=mal[b[i]];j>=mal[a[i]];j--){
                	ll x=get(j);
                	update(j+1,x);
                	//update2(j,x);
                	tree2[j]+=x;
                if(j!=mal[a[i]]){
                	ll x=(get(j-1)+ tree2[j-1])%MOD;
                	update(j,((x%MOD)*((maa[j]-maa[j-1]-1) % MOD))%MOD);
                }
            }
 
        }
        cout << ans;
        return 0;
    }

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