oj.uz

Submission #200797

# Submission time Handle Problem Language Result Execution time Memory
200797 2020-02-08T07:30:10 Z Nordway Boat (APIO16_boat) C++14
9 / 100
 786 ms 524292 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

template<class T,int SZ> struct BIT{
  T t[SZ];
  void upd(int x,T y){
    for(int i=x;i<SZ;i=(i|(i+1))){
      t[i]+=y;
    }
  }
  T pref(int x){
    T res=0;
    for(int i=x;i>=0;i=(i&(i+1))-1){
      res+=t[i];
    }
    return res;
  }
  T get(int l,int r){
    return pref(r)-pref(l-1);
  }
};
template<class T,int SZ> struct ST{
  T t[4*SZ];
  void build(T a[],int v,int tl,int tr){
    if(tl==tr){
      t[v]=a[tl];
      return ;
    }
    int tm=(tl+tr)/2;
    build(a,v*2,tl,tm);
    build(a,v*2+1,tm+1,tr);
    t[v]=t[v*2]+t[v*2+1];
  }
  void upd(int v,int tl,int tr,int pos,T val){
    if(tl==tr){
      t[v]+=val;
      return ;
    }
    int tm=(tl+tr)/2;
    if(pos<=tm)upd(v*2,tl,tm,pos,val);
    else upd(v*2+1,tm+1,tr,pos,val);
    t[v]=t[v*2]+t[v*2+1];
  }
  T get(int v,int tl,int tr,int l,int r){
    if(tl>r||l>tr)return 0;
    if(l<=tl&&tr<=r)return t[v];
    int tm=(tl+tr)/2;
    return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r);
  }
};

const int N=1e4+11;
const int M=1e3+11;
const int W=1e3+11;
const int inf=INT_MAX;
const ll INF=1e18;
const ll mod=1e9+7;
const ld EPS=1e-9;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};

int a[N],b[N];
ll dp[N];
map<int,int>val;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  vector<int>v;
  for(int i=1;i<=n;i++){
    cin>>a[i]>>b[i];
    for(int j=a[i];j<=b[i];j++){
      v.pb(j);
    }
  }
  sort(all(v));
  val[v[0]]=1;
  int cnt=0;
  for(int i=1;i<sz(v);i++){
    if(v[i]==v[i-1])continue;
    val[v[i]]=val[v[i-1]]+1;
    cnt=val[v[i]];
  }
  dp[0]=1;
  for(int i=1;i<=n;i++){
    ll sum=0;
    int l=val[a[i]];
    int r=val[b[i]];
    for(int j=0;j<l;j++){
      sum+=dp[j];
      sum%=mod;
    }
    for(int j=l;j<=r;j++){
      dp[j]+=sum;
      dp[j]%=mod;
      sum=dp[j];
    }
  }
  ll ans=0;
  for(int i=1;i<=cnt;i++){
    ans+=dp[i];
    ans%=mod;
  }
  cout<<ans;

}

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 380 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 56 ms 4584 KB Output is correct
22 Correct 68 ms 4584 KB Output is correct
23 Correct 52 ms 4584 KB Output is correct
24 Correct 55 ms 4588 KB Output is correct
25 Correct 58 ms 4588 KB Output is correct
26 Correct 78 ms 4584 KB Output is correct
27 Correct 58 ms 4588 KB Output is correct
28 Correct 59 ms 4584 KB Output is correct
29 Correct 58 ms 4584 KB Output is correct
30 Runtime error 622 ms 102612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 786 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 380 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 56 ms 4584 KB Output is correct
22 Correct 68 ms 4584 KB Output is correct
23 Correct 52 ms 4584 KB Output is correct
24 Correct 55 ms 4588 KB Output is correct
25 Correct 58 ms 4588 KB Output is correct
26 Correct 78 ms 4584 KB Output is correct
27 Correct 58 ms 4588 KB Output is correct
28 Correct 59 ms 4584 KB Output is correct
29 Correct 58 ms 4584 KB Output is correct
30 Runtime error 622 ms 102612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -