Submission #361928

#	Time	Username	Problem	Language	Result	Execution time	Memory
361928		AlexLuchianov	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	688 ms	22920 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int const inf = 1000000000;

struct Card{
  int x;
  int y;
  int id;
  bool operator < (Card oth) const {
    return y < oth.y;
  }
} v[1 + nmax];

int base[1 + nmax];
struct Node{
  int smin;
  int coef;
  int id;
  Node operator + (Node const oth) const{
    Node result;
    if(smin <= oth.smin) {
      result.smin = smin; 
      result.id = id;
      result.coef = coef;
    } else if(oth.smin < smin) { 
      result.smin = oth.smin;
      result.coef = oth.coef;
      result.id = oth.id;
    }
    return result;
  }
};

class SegmentTree{
  public:
    std::vector<Node> aint;
    std::vector<int> lazy;
    SegmentTree(int n) {
      aint.resize(1 + 4 * n);
      lazy.resize(1 + 4 * n);
    }
    void cleannode(int node, int from, int to) {
      if(from < to) {
        int mid = (from + to) / 2;
        lazy[node * 2] ^= lazy[node];
        lazy[node * 2 + 1] ^= lazy[node];
      }
      aint[node].coef ^= lazy[node];
      lazy[node] = 0;
    }

    void update(int node, int from, int to, int x , int y, int val) {
      if(from == x && to == y) {
        lazy[node] ^= val;
        cleannode(node, from, to);
      } else {
        int mid = (from + to) / 2;
        cleannode(node * 2, from, mid);
        cleannode(node * 2 + 1, mid + 1, to);

        if(from <= mid)
          update(node * 2, from, mid, x, std::min(y, mid), val);
        if(mid + 1 <= y)
          update(node * 2 + 1, mid + 1, to, std::max(x, mid + 1), y, val);
        aint[node] = aint[node * 2] + aint[node * 2 + 1];
      }
    }
    Node query(int node, int from, int to, int x, int y) {
      cleannode(node, from, to);
      if(from == x && to == y)
        return aint[node];
      else {
        int mid = (from + to) / 2;
        if(x <= mid && y <= mid)
          return query(node * 2, from, mid, x, y);
        else if(mid + 1 <= x && mid + 1 <= y)
          return query(node * 2 + 1, mid + 1, to, x, y);
        else
          return query(node * 2, from, mid, x, mid) + query(node * 2 + 1, mid + 1, to, mid + 1, y);
      }
    }

    void setvalue(int node, int from, int to, int x, Node val) {
      if(from < to) {
        int mid = (from + to) / 2;
        cleannode(node * 2, from, mid);
        cleannode(node * 2 + 1, mid + 1, to);

        if(x <= mid)
          setvalue(node * 2, from, mid, x, val);
        else
          setvalue(node * 2 + 1, mid + 1, to, x, val);
        aint[node] = aint[node * 2] + aint[node * 2 + 1];
      } else
        aint[node] = val;
    }
};


int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, q;
  std::cin >> n >> q;
  for(int i = 1;i <= n; i++) {
    std::cin >> v[i].x >> v[i].y;
    v[i].id = i;
    if(v[i].y < v[i].x) {
      base[i] = 1;
      std::swap(v[i].x, v[i].y);
    }
  }
  std::sort(v + 1, v + n + 1);
  std::vector<int> queries;
  for(int i = 1;i <= q; i++) {
    int val;
    std::cin >> val;
    queries.push_back(val);
  }
  SegmentTree aint(n);
  for(int i = 1;i <= n; i++)
    aint.setvalue(1, 1, n, i, {v[i].x, 0, i});

  std::reverse(queries.begin(), queries.end());

  ll result = 0;

  for(int i = 0; i < queries.size(); i++) {
    int x = 0;
    int target = queries[i];
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(x + jump <= n && v[x + jump].y <= target)
        x += jump;
    if(0 < x)
      aint.update(1, 1, n, 1, x, 1);
    if(x < n) {
      bool flag;
      do {
        flag = false;
        Node oth = aint.query(1, 1, n, x + 1, n);
        if(oth.smin <= target) {
          flag = true;
          aint.setvalue(1, 1, n, oth.id, {inf + 1, 0, 0});
          if(oth.coef == 0)
            result += v[oth.id].y;
          else
            result += v[oth.id].x;
        }
      } while(flag);
    }
  }

  bool flag;
  do {
    flag = false;
    Node oth = aint.query(1, 1, n, 1, n);
    if(oth.smin <= inf) {
      flag = true;
      aint.setvalue(1, 1, n, oth.id, {inf + 1, 0, 0}); 
      oth.coef ^= base[v[oth.id].id];
      if(oth.coef == 1)
        result += v[oth.id].y;
      else
        result += v[oth.id].x;
    }
  } while(flag);
  std::cout << result; 
  return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void SegmentTree::cleannode(int, int, int)':
fortune_telling2.cpp:53:13: warning: unused variable 'mid' [-Wunused-variable]
   53 |         int mid = (from + to) / 2;
      |             ^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i = 0; i < queries.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

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