oj.uz

Submission #200798

# Submission time Handle Problem Language Result Execution time Memory
200798 2020-02-08T07:30:47 Z Nordway Boat (APIO16_boat) C++14
31 / 100
 1426 ms 524288 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=1e6+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 380 KB Output is correct
5 Correct 6 ms 380 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 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 7 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 424 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 396 KB Output is correct
20 Correct 5 ms 376 KB Output is correct

Subtask #2
22.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 380 KB Output is correct
5 Correct 6 ms 380 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 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 7 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 424 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 396 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 59 ms 4716 KB Output is correct
22 Correct 56 ms 4600 KB Output is correct
23 Correct 59 ms 4584 KB Output is correct
24 Correct 61 ms 4560 KB Output is correct
25 Correct 64 ms 4584 KB Output is correct
26 Correct 77 ms 4584 KB Output is correct
27 Correct 68 ms 4588 KB Output is correct
28 Correct 59 ms 4584 KB Output is correct
29 Correct 69 ms 4588 KB Output is correct
30 Correct 1412 ms 58424 KB Output is correct
31 Correct 1421 ms 57416 KB Output is correct
32 Correct 1409 ms 58500 KB Output is correct
33 Correct 1426 ms 56944 KB Output is correct
34 Correct 1397 ms 57448 KB Output is correct
35 Correct 1343 ms 54840 KB Output is correct
36 Correct 1373 ms 56920 KB Output is correct
37 Correct 1405 ms 57296 KB Output is correct
38 Correct 1354 ms 55540 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 937 ms 524288 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 380 KB Output is correct
5 Correct 6 ms 380 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 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 7 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 424 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 396 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 59 ms 4716 KB Output is correct
22 Correct 56 ms 4600 KB Output is correct
23 Correct 59 ms 4584 KB Output is correct
24 Correct 61 ms 4560 KB Output is correct
25 Correct 64 ms 4584 KB Output is correct
26 Correct 77 ms 4584 KB Output is correct
27 Correct 68 ms 4588 KB Output is correct
28 Correct 59 ms 4584 KB Output is correct
29 Correct 69 ms 4588 KB Output is correct
30 Correct 1412 ms 58424 KB Output is correct
31 Correct 1421 ms 57416 KB Output is correct
32 Correct 1409 ms 58500 KB Output is correct
33 Correct 1426 ms 56944 KB Output is correct
34 Correct 1397 ms 57448 KB Output is correct
35 Correct 1343 ms 54840 KB Output is correct
36 Correct 1373 ms 56920 KB Output is correct
37 Correct 1405 ms 57296 KB Output is correct
38 Correct 1354 ms 55540 KB Output is correct
39 Runtime error 937 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -