oj.uz

Submission #124344

# Submission time Handle Problem Language Result Execution time Memory
124344 2019-07-03T06:49:38 Z Mtaylor Boat (APIO16_boat) C++17
9 / 100
 2000 ms 223452 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];
    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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 510 ms 1372 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 510 ms 1372 KB Output isn't correct
22 Halted 0 ms 0 KB -