Submission #1312578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312578		reginox	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	1 ms	332 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
struct Fenwick{
	int n; vector<vector<ll>> t;
    void resize(int _n){
		n = _n;
        t.assign(n+1, vector<ll>(2, 0));
    }
	void upd(int tp, int id, ll x){
		for(int i = id; i <= n; i+=i&(-i)) t[i][tp]+=x;
	}
	void add(int l, int r, ll x){
		upd(0, l, x); upd(0, r+1, -x);
		upd(1, l, x*(l-1)); upd(1, r+1, -x*r);	
	}
	ll sum(int tp, int id){
		ll res = 0;
		for(int i = id; i > 0; i-=i&(-i)) res+=t[i][tp];
		return res;
	}
	ll get(int x){
		return sum(0, x)*(ll)x  - sum(1, x);
	}
	ll query(int a, int b){
		return get(b) - get(a-1);
	}
};

const int N = 2e5+3;
int n, k, t[N];
pair<pair<int, int>, int> a[N];
Fenwick f;
int sr[N];

int tr[N]; //min on segment

void update(int id, int l, int r, int u, int v){
  if(u < l || r < u) return ;
  if(l == r){
    tr[id] = v;
    return ;
  }
  int mid = (l+r)/2;
  update(id*2, l, mid, u, v);
  update(id*2+1, mid+1, r, u, v);
  tr[id] = max(tr[id*2], tr[id*2+1]);
}

int query(int id, int l, int r, int u, int v){
  if(v < l || r < u) return -1e9;
  if(u <= l && r <= v) return tr[id];
  int mid = (l+r)/2;
  return max(query(id*2, l, mid, u, v), query(id*2+1, mid+1, r, u, v));
}

int walk(int id, int l, int r, int u){
  if(tr[id] < u) return -1;
  if(l == r) return l;
  int mid = (l+r)/2;
  if(tr[id*2+1] >= u) return walk(id*2+1, mid+1, r, u);
  else return walk(id*2, l, mid, u);
}

int o[N];

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> a[i].first.first >> a[i].first.second;
    a[i].second = a[i].first.first;
    if(a[i].first.first > a[i].first.second) swap(a[i].first.first, a[i].first.second);
  }
  for(int i = 1; i <= k; i++) cin >> t[i];
  sort(a+1, a+n+1, [&](pair<pi, int> a, pair<pi, int> b){
    return a.first.second > b.first.second;
  });
  for(int i = 1; i <= k; i++) sr[i] = i;
  for(int i = 1; i <= k; i++) update(1, 1, k, i, t[i]);
  sort(sr+1, sr+k+1, [&](int a, int b){
    return t[a] > t[b];
  });
  f.resize(k);
  int pt = 1; ll res = 0;
  for(int i = 1; i <= n; i++){
    //update all b[i] <= t[...]
    while(pt <= n && t[sr[pt]] >= a[i].first.second){
      f.add(sr[pt], sr[pt], 1);
      update(1, 1, k, sr[pt], -1);
      pt++;
    }

    //first id so a[i] <= t[id]
    int id = walk(1, 1, k, a[i].first.first), cnt, add;
    if(id == -1){
      //all a[i] >= t[id]
      cnt = f.query(1, k);
      if(cnt & 1) add = a[i].second ^ a[i].first.first ^ a[i].first.second;
      else add = a[i].second;
    }
    else{
      cnt = f.query(id+1, k);
      if(cnt & 1) add = a[i].first.first;
      else add = a[i].first.second;
    }
    res += add;
    // cout << a[i].first.first << " " << a[i].first.second << " " << a[i].second << "\n";
    // for(int i = 1; i <= k; i++) cout << query(1, 1, k, i, i) << " ";
    // cout << "\n";
    // for(int i = 1; i <= k; i++) cout << f.query(i, i) << " ";
    // cout << "\n";
    // cout << id << " " << cnt << " " << add << "\n\n";
  }
  cout << res;
  return 0;
}

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