Submission #1046331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046331		Armin	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	2 ms	10844 KiB

fortune_telling2

/// ITNOG
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;

template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 32008, SQ = 110, INF = 1e9, LGN = 20, mod = 998244353, P = 131113;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct fenwick {
  int fen[N];
  void upd (int ind, int val){
    ind += 3;
    for (; ind < N; ind += ind & (-ind)){
      fen[ind] += val;
    }
  }
  int gett (int ind){
    ind += 3;
    int ret = 0;
    for (; ind; ind -= ind & (-ind)){
      ret += fen[ind];
    }
    return ret;
  }
};

int n, k, ans, node[(3 * N) << 2], g[3 * N];
pii p[N], t[N];
vector <int> prs;
unordered_map <int, int> m;
fenwick fen;

void upd (int ind ,int val, int lx = 0, int rx = 3 * N, int x = 1){
  if (rx - lx == 1){
    node[x] = max (node[x], val);
    return;
  }
  int md = (lx + rx) >> 1;
  if (ind < md){
    upd (ind, val, lx, md, x << 1);
  }
  else {
    upd (ind, val, md, rx, x << 1 | 1);
  }
  node[x] = max (node[x << 1], node[x << 1 | 1]);
  return;
}

int gett (int l, int r, int lx = 1, int rx = 3 * N, int x = 1){
  if (l <= lx && rx <= r){
    return node[x];
  }
  if (l >= rx || lx >= r){
    return 0;
  }
  int md = (lx + rx) >> 1;
  return max (gett (l, r, lx, md, x << 1), gett (l, r, md, rx, x << 1 | 1));
}

int32_t main(){
  fast_io;
  cin >> n >> k;
  for (int i = 0; i < n; ++ i){
    cin >> p[i].F >> p[i].S;
    prs.pb(p[i].F);
    prs.pb(p[i].S);
  }
  sort (p, p + n, [&](pii p1, pii p2) {return max (p1.F, p1.S) > max (p2.F, p2.S);});
  for (int i = 0; i < k; ++ i){
    cin >> t[i].F;
    prs.pb(t[i].F);
    t[i].S = i + 1;
  }
  sort (t, t + k, [&](pii t1, pii t2) {return t1.F > t2.F;});
  sort (all(prs));
  prs.resize(unique(all(prs)) - prs.begin());
  for (int i = 0; i < prs.size(); ++ i){
    m[prs[i]] = i + 1;
    g[i+1] = prs[i];
  }
  for (int i = 0; i < n; ++ i){
    p[i].F = m[p[i].F];
    p[i].S = m[p[i].S];
  }
  for (int i = 0; i < k; ++ i){
    t[i].F = m[t[i].F];
  }
  for (int i = 0; i < k; ++ i){
    upd (t[i].F, t[i].S);
  }
  int pt = 0;
  for (int i = 0; i < n; ++ i){
    while (pt < k && t[pt].F >= max (p[i].F, p[i].S)){
      fen.upd(t[pt].S, 1);
      ++ pt;
    }
    int lst = 0;
    if (p[i].F != p[i].S){
      lst = gett (min (p[i].F, p[i].S), max (p[i].F, p[i].S));
    }
    if (lst == 0){
      ans += (fen.gett (N - 4) & 1 ? g[p[i].S] : g[p[i].F]);
    }
    else {
      if (p[i].F > p[i].S){
        swap (p[i].F, p[i].S);
      }
      ans += ((fen.gett (N - 4) - fen.gett (lst)) & 1 ? g[p[i].F] : g[p[i].S]);
    }
  }
  cout << ans << '\n';
  return 0;
}

// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:114:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = 0; i < prs.size(); ++ i){
      |                   ~~^~~~~~~~~~~~

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