Submission #200879

#	Time	Username	Problem	Language	Result	Execution time	Memory
200879		quocnguyen1012	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	522 ms	28896 KiB

fortune_telling2

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;

class segment_tree
{
#define lc id << 1
#define rc id << 1 | 1
  vector<int> ST;
public:
  segment_tree(int n)
  {
    ST.assign(4 * n + 5, 0);
  }
  void update(int id, int l, int r, int pos, int val)
  {
    if (l > pos || r < pos) return;
    if (l == r){
      ST[id] = val;
      return;
    }
    int mid = (l + r) / 2;
    update(lc, l, mid, pos, val); update(rc, mid + 1, r, pos, val);
    ST[id] = max(ST[lc], ST[rc]);
  }
  int query(int id, int l, int r, int L, int R)
  {
    if (l > R || L > r) return 0;
    if (L <= l && r <= R) return ST[id];
    int mid = (l + r) / 2;
    return max(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
  }
};

class fenwick_tree
{
  vector<int> cnt; int n;
public:
  fenwick_tree(int _n)
  {
    n = _n;
    cnt.assign(n + 5, 0);
  }
  void update(int i, int v)
  {
    for (; i; i -= i & -i){
      cnt[i] += v;
    }
  }
  int sum(int i)
  {
    int res = 0;
    for (; i <= n; i += i & -i){
      res += cnt[i];
    }
    return res;
  }
};

int N, M;
int a[maxn], b[maxn], c[maxn];
vector<int> val;
vector<int> query[maxn];

int compress(int x)
{
  return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M;
  for (int i = 1; i <= N; ++i){
    cin >> a[i] >> b[i];
    val.pb(a[i]); val.pb(b[i]);
  }
  for (int i = 1; i <= M; ++i){
    cin >> c[i];
    val.pb(c[i]);
  }
  sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
  segment_tree ST(val.size() + 5);
  fenwick_tree FT(val.size() + 5);
  for (int i = 1; i <= M; ++i){
    c[i] = compress(c[i]);
    ST.update(1, 1, val.size(), c[i], i);
  }
  ll res = 0;
  for (int i = 1; i <= N; ++i){
    if (a[i] == b[i]){
      res += a[i];
      continue;
    }
    a[i] = compress(a[i]);
    b[i] = compress(b[i]);
    int t = ST.query(1, 1, val.size(), min(a[i], b[i]), max(a[i], b[i]) - 1);
    if (t && a[i] < b[i]) swap(a[i], b[i]);
    query[t].pb(i);
  }
  for (int i = M; i >= 0; --i){
    for (auto id : query[i]){
      int v = FT.sum(max(a[id], b[id]));
      if (v & 1) swap(a[id], b[id]);
      res += val[a[id] - 1];
    }
    if (i) FT.update(c[i], 1);
  }
  cout << res << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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