oj.uz

Submission #61171

# Submission time Handle Problem Language Result Execution time Memory
61171 2018-07-25T09:52:50 Z Flugan42 Boat (APIO16_boat) C++14
0 / 100
 5 ms 488 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef long double lld;
#define rep(i,a,b) for(ll i = a; i < b; i++)
#define per(i,a,b) for(ll i = a; i >= b; i--)
#define inf 1000000000000000000
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto a : x)

const ll mod = 1000000007;
ll n;
vi a,b,s,v;
set<ll> vals;

class segT {
private:
  ll n;
  vi tree,A;
  ll left(ll v) { return 2*v; }
  ll right(ll v) { return 2*v+1; }
  void build(ll p, ll l, ll r){
    if (l == r) tree[p] = (A[l]%mod);
    else {
      build(left(p),l,(l+r)/2);
      build(right(p),(l+r)/2+1,r);
      tree[p] = (tree[left(p)]+tree[right(p)])%mod;
    }
  }
  ll rsq(ll p, ll l, ll r, ll i, ll j){
    if (l > j || r < i) return 0;
    if (i <= l && r <= j) return (tree[p]%mod);
    ll p1 = rsq(left(p),l,(l+r)/2,i,j);
    ll p2 = rsq(right(p),(l+r)/2+1,r,i,j);
    return (p1+p2)%mod;
  }
  void update(ll p, ll l, ll r, ll i, ll val){
    if (i < l || r < i) return;
    if (l == r) {
      tree[p] = (A[l]%mod);
    } else {
      update(left(p),l,(l+r)/2,i,val);
      update(right(p),(l+r)/2+1,r,i,val);
      tree[p] = (tree[left(p)]+tree[right(p)])%mod;
    }
  }
public:
  void build(vi &_a){
    n = sz(_a);
    A = _a;
    tree.assign(4*n+10,0);
  }
  ll rsq(ll i, ll j) { return rsq(1,0,n-1,i,j); }
  void update(ll i, ll val){
    A[i] = (val%mod);
    update(1,0,n-1,i,val);
  }
} ;

int main(){
  cin >> n;
  a.assign(n,0); b.assign(n,0);
  rep(i,0,n) {
    cin >> a[i] >> b[i];
    assert(b[i]-a[i] < 1000010);
    per(j,b[i],a[i]) { vals.insert(j); s.push_back(j); }
  }

  trav(x,vals) v.push_back(x);
  sort(all(v));
  vi dp; dp.assign(sz(v),0);
  segT mytree;
  mytree.build(dp);

  map<ll,ll> inv;
  rep(i,0,sz(v)){ inv.insert(make_pair(v[i],i)); }
  rep(i,0,sz(s)){
    if (s[i] == 0) dp[inv[s[i]]] = ((dp[inv[s[i]]]+1)%mod);
    else {
      dp[inv[s[i]]] = (1+dp[inv[s[i]]]+mytree.rsq(0,inv[s[i]]-1))%mod;
      mytree.update(inv[s[i]],dp[inv[s[i]]]);
    }
  //  cout << s[i] << " " << inv[s[i]] << " " << dp[inv[s[i]]] << endl;
  }
  ll res = 0;
  rep(i,0,sz(dp)) { res += dp[i]; }
  cout << res << endl;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 488 KB Execution killed with signal 11 (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 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -