Submission #540170

#	Time	Username	Problem	Language	Result	Execution time	Memory
540170		cig32	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	3068 ms	3120 KiB

fortune_telling2

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
struct query {
  int a, b;
  int mi, ma;
};
bool cmp(query x, query y) {
  return x.ma < y.ma;
}

struct segtree {
  struct node {
    int mi, cntmi;
    int ma, cntma;
  };
  vector<node> st;
  int stok;

  void bu(int l, int r, int idx) {
    if(l == r) {
      st[idx].mi = 0;
      st[idx].ma = 0;
      st[idx].cntmi = 1;
      st[idx].cntma = 1;
      return;
    }
    int mid = (l + r) >> 1;
    bu(l, mid, 2*idx+1);
    bu(mid+1, r, 2*idx+2);
    st[idx].mi = 0, st[idx].ma = 0;
    st[idx].cntmi = st[2*idx+1].cntmi + st[2*idx+2].cntmi;
    st[idx].cntma = st[2*idx+1].cntma + st[2*idx+2].cntma;
  }

  void u(int l, int r, int tar, int idx, int val) {
    if(l == r) {
      st[idx].mi = st[idx].ma = val;
      return;
    }
    int mid = (l+r) >> 1;
    if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
    else u(mid+1, r, tar, 2*idx+2, val);
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
    if(st[2*idx+1].mi == st[2*idx+2].mi) st[idx].cntmi = st[2*idx+1].cntmi + st[2*idx+2].cntmi;
    else st[idx].cntmi = (st[2*idx+1].mi < st[2*idx+2].mi ? st[2*idx+1].cntmi : st[2*idx+2].cntmi);
    if(st[2*idx+1].ma == st[2*idx+2].ma) st[idx].cntma = st[2*idx+1].cntma + st[2*idx+2].cntma;
    else st[idx].cntma = (st[2*idx+1].ma > st[2*idx+2].ma ? st[2*idx+1].cntma : st[2*idx+2].cntma);
  }

  int qu1(int l, int r, int constl, int constr, int idx, int val) {
    if(l <= constl && constr <= r) {
      if(st[idx].ma < val) return -1;
      while(constl < constr) {
        int mid = (constl +constr) >> 1;
        if(st[2*idx+2].ma >= val) constl = mid + 1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    if(mid < l || r <constl) return qu1(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1, val);
    else {
      int res = qu1(l, r, mid+1, constr, 2*idx+2, val);
      if(res != -1) return res;
      return qu1(l, r, constl, mid, 2*idx+1, val);
    }
  }

  pair<int, int> qu2(int l, int r, int constl, int constr, int idx) {
    if(l<=constl && constr<=r) return {st[idx].mi, st[idx].cntmi};
    int mid = (constl +constr) >> 1;
    if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r <mid+1) return qu2(l,r ,constl, mid, 2*idx+1);
    else {
      pair<int, int> lchild = qu2(l, r, constl, mid, 2*idx+1);
      pair<int, int> rchild = qu2(l, r, mid+1, constr, 2*idx+2);
      if(lchild != rchild) return min(lchild, rchild);
      else return {lchild.first, lchild.second + rchild.second};
    }
  }
  public:
  void resize(int k) {
    stok = k;
    st.resize(4*k + 10);
  }
  void build() {
    bu(1, stok, 0);
  }

  void point_update(int i, int v) {
    u(1, stok, i, 0, v);
  }
  int last_atleast(int l, int r, int v) {
    return qu1(l, r, 1, stok, 0, v);
  }
  pair<int, int> min_cnt(int l, int r) {
    return qu2(l, r, 1, stok, 0);
  }
};

void solve(int tc) {
  segtree st;
  int n, k;
  cin >> n >> k;
  int a[n+1], b[n+1]; char c[n+1];
  for(int i=1; i<=n; i++) {
    cin >> a[i] >> b[i];
    c[i] = 'a';
  }
  for(int i=1; i<=k; i++) {
    int q; cin >> q;
    for(int j=1; j<=n; j++) {
      if(c[j] == 'a') {
        if(a[j] <= q) c[j] = 'b';
      }
      else {
        if(b[j] <= q) c[j] = 'a';
      }
    }
  }
  int ans = 0;
  for(int i=1; i<=n; i++) ans += (c[i] == 'a' ? a[i] : b[i]);
  cout << ans << '\n';
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 
/*
1 3
4 6
8
2
9
*/

• Subtask 1: 4 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65