oj.uz

Submission #124250

# Submission time Handle Problem Language Result Execution time Memory
124250 2019-07-02T22:04:42 Z Mtaylor Boat (APIO16_boat) C++17
0 / 100
 4 ms 504 KB 
#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];

    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];
            ss.insert(a[i]);
            ss.insert(b[i]);
        }
        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);
                }
                ans%=MOD;
            }
            for(int j=mal[a[i]]+1;j<=mal[b[i]];j++){
                update(j,maa[j]-maa[j-1]);
                ans%=MOD;
            }
            //cout << ans << endl;
            update(mal[b[i]]+1,1);

        }
        cout << ans;
        return 0;
    }

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -