Submission #61183

#	Time	Username	Problem	Language	Result	Execution time	Memory
61183		Flugan42	Boat (APIO16_boat)	C++14	31 / 100	1353 ms	158928 KiB

boat

#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);

  unordered_map<ll,ll> inv;
  rep(i,0,sz(v)){ inv.insert(make_pair(v[i],i)); }
  rep(i,0,sz(s)){
    if (inv[s[i]] == 0) {
      dp[inv[s[i]]] = ((dp[inv[s[i]]]+1)%mod);
      mytree.update(inv[s[i]],dp[inv[s[i]]]);
    }
    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 = (res+dp[i])%mod; }
  cout << res << endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42