Submission #728231

#	Time	Username	Problem	Language	Result	Execution time	Memory
728231		jampm	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1529 ms	86932 KiB

fortune_telling2

    #include <bits/stdc++.h>
    using namespace std;
    using pii = pair<int, int>;
    using ll = long long int;
    #define all(a) a.begin(), a.end()
    const int Mxn = 6e5 + 2;
     
    struct segtree_sum {
      vector<int> segs;
      segtree_sum() {segs.assign(Mxn<<1, 0);}
      void upd(int i, int x) {
        i += Mxn; segs[i] += x;
        for (i >>= 1; i; i >>= 1) {
          segs[i] = segs[i<<1] + segs[i<<1|1];
        }
      }
      int query(int l, int r, int ans = 0) {
        for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
          if (l&1) ans += segs[l++];
          if (r&1) ans += segs[--r];
        }
        return ans;
      }
    };
     
    struct segtree_max {
      vector<int> segs;
      segtree_max() {segs.assign(Mxn<<1, -1);}
      void upd(int i, int x) {
        i += Mxn; segs[i] = x;
        for (i >>= 1; i; i >>= 1) {
          segs[i] = max(segs[i<<1], segs[i<<1|1]);
        }
      }
      int query(int l, int r, int ans = -1) {
        for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
          if (l&1) ans = max(segs[l++], ans);
          if (r&1) ans = max(segs[--r], ans);
        }
        return ans;
      }
    };
     
    struct query {
      int idx, sufix, val;
      bool operator<(const query & X) {return sufix > X.sufix;}
    };
     
    int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int n, k, cnt = 0; cin >> n >> k; 
      ll ans = 0;
      map<int, int> cc;
      map<ll, ll> anti;
      vector<pii> A(n);
      for (auto &[x, y] : A) cin >> x >> y;
      vector<int> T(k);
      for (auto &e : T) cin >> e;
      for (auto [x, y] : A) cc[x], cc[y];
      for (auto e : T) cc[e];
      for (auto &[x, y] : cc) y = cnt++;
      for (auto &[x, y] : A) x = cc[x], y = cc[y];
      for (auto &e : T) e = cc[e];
      for (auto [x, y] : cc) anti[y] = x;
     
      segtree_max St_max;
      vector<query> Count(n);
      for (int i = 0; i < k; i++) {
        St_max.upd(T[i], i);
      }
      for (int i = 0; i < n; i++) {
        auto &[idx, sufix, val] = Count[i];
        idx = i;
        auto [l, r] = A[i];
        if (l > r) {
          sufix = St_max.query(r, l - 1);
          val = l;
        } else {
          sufix = St_max.query(l, r - 1);
          val = r;
        }
      }
      sort(all(Count));
      cnt = 0;
      segtree_sum St_sum; vector<int> Ans(n);
      for (int i = k - 1; i >= 0; i--) {
        while (cnt < n && Count[cnt].sufix == i) {
          auto &[idx, sufix, val] = Count[cnt++];
          Ans[idx] = St_sum.query(val, Mxn - 1);
        }
        St_sum.upd(T[i], 1);
      }
      for (int i = 0; i < n; i++) {
        auto [l, r] = A[i];
        if (l > r) {
          swap(l, r);
          if (St_max.query(l, r - 1) == -1) {
            if (St_sum.query(r, Mxn - 1)&1) ans += anti[l];
            else ans += anti[r];
          } else {
            if (Ans[i]&1) ans += anti[l];
            else ans += anti[r];
          }
        } else {
          if (St_max.query(l, r - 1) == -1) {
            if (St_sum.query(r, Mxn - 1)&1) ans += anti[r];
            else ans += anti[l];
          } else {
            if (Ans[i]&1) ans += anti[l];
            else ans += anti[r];
          }
        }
      }
      cout << ans << '\n';
    }

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