제출 #540171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540171		cig32	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	220 ms	42884 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.first != rchild.first) 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;
  st.resize(k);
  st.build();
  query q[n];
  for(int i=0; i<n; i++) {
    cin >> q[i].a >> q[i].b;
    q[i].mi = min(q[i].a, q[i].b);
    q[i].ma = max(q[i].a, q[i].b);
  }
  sort(q, q+n, cmp);
  vector<pair<int, int> > v;
  for(int i=1; i<=k; i++) {
    int y;
    cin >> y;
    v.push_back({y, i});
  }
  sort(v.begin(), v.end());
  int vptr = 0;
  int res = 0;
  for(int i=0; i<n; i++) {
    
    int og = res;
    while(vptr != v.size() && v[vptr].first < q[i].ma) {
      st.point_update(v[vptr].second, v[vptr].first);
      //cout << "st[" << v[vptr].second << "] := " << v[vptr].first << "\n";
      vptr++;
    }
    //cout << "original: " << q[i].a << ", final: ";
    int idx = st.last_atleast(1, k, q[i].mi);
    if(idx == -1) { // A operations only
      pair<int, int> ono = st.min_cnt(1, k);
      if(ono.first == 0 && ono.second % 2 == 1) { // changed
        res += q[i].b;
      }
      else {
        res += q[i].a;
      }
    }
    else if(q[i].a == q[i].b) { // doesn't matter
      res += q[i].a;
    }
    else if(idx + 1 > k) { // last operation is S
      res += q[i].ma;
    }
    else { 
      //cout << "!!! " << idx << " ";
      pair<int, int> ono = st.min_cnt(idx + 1, k);
      //cout << ono.second << " ";
      if(ono.first == 0 && ono.second % 2 == 1) { // changed
        res += q[i].mi;
      }
      else {
        res += q[i].ma;
      }
    }
    //cout << res - og << '\n';
  }
  cout << res << '\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);
} 
/*
6 6
1 13
14 23
5 17
10 23
6 10
12 18
10
20
19
17
21
30
*/

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'void solve(long long int)':
fortune_telling2.cpp:156:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     while(vptr != v.size() && v[vptr].first < q[i].ma) {
      |           ~~~~~^~~~~~~~~~~
fortune_telling2.cpp:155:9: warning: unused variable 'og' [-Wunused-variable]
  155 |     int og = res;
      |         ^~

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