Submission #787202

#	Time	Username	Problem	Language	Result	Execution time	Memory
787202		tvladm2009	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	419 ms	19700 KiB

kyoto

#include <bits/stdc++.h>
#define int ll

using namespace std;

typedef long long ll;
typedef long double ld;
const int N = (int) 1e5 + 7;
int a[N];
int b[N];
int h;
int w;

struct Fraction {
  ll a;
  ll b;

  Fraction(ll a, ll b) : a(a), b(b) {

  }
};

ld getld(Fraction fr) {
  return (ld)fr.a / (ld)fr.b;
}

bool operator < (Fraction First, Fraction Second) {
  return (ld)First.a / (ld)First.b <= (ld)Second.a / (ld)Second.b;
}

bool operator == (Fraction First, Fraction Second) {
  return (ld)First.a / (ld)First.b == (ld)Second.a / (ld)Second.b;
}

Fraction operator + (Fraction First, ll Second) {
  return Fraction(First.a + Second * First.b, First.b);
}

Fraction operator + (ll Second, Fraction First) {
  return Fraction(First.a + Second * First.b, First.b);
}

Fraction operator - (Fraction First, ll Second) {
  return Fraction(First.a - Second * First.b, First.b);
}

Fraction operator - (ll Second, Fraction First) {
  return Fraction(-First.a + Second * First.b, First.b);
}

Fraction operator * (Fraction First, ll Second) {
  return {First.a * Second, First.b};
}

Fraction operator * (ll First, Fraction Second) {
  return {Second.a * First, Second.b};
}

struct T {
  Fraction val;
  int ind;
  bool type;
};

bool operator == (T a, T b) {
  return a.val.a == b.val.a && a.val.b == b.val.b && a.ind == b.ind && a.type == b.type;
}

bool operator < (T a, T b) {
  if ((a.val == b.val) == false) {
    return a.val < b.val;
  }
  if (a.ind != b.ind) {
    return a.ind < b.ind;
  }
  return a.type < b.type;
}

struct BIT {
  vector<int> aib;
  int n;

  BIT(int nn) {
    n = nn;
    aib.resize(n + 1);
  }

  void update(int x, int val) {
    for (int i = x; i <= n; i += i & -i) {
      aib[i] += val;
    }
  }

  int query(int x) {
    int ret = 0;
    for (int i = x; i >= 1; i -= i & -i) {
      ret += aib[i];
    }
    return ret;
  }

  int getprev(int x) {
    if (query(x - 1) == 0) {
      return -1;
    }
    int need = query(x - 1);
    int sol = 0;
    int sum = 0;
    for (int b = 20; b >= 0; b--) {
      if (sol + (1 << b) < x && sum + aib[sol + (1 << b)] < need) {
        sum += aib[sol + (1 << b)];
        sol += (1 << b);
      }
    }
    return sol + 1;
  }

  int getnext(int x) {
    if (query(n) - query(x) == 0) {
      return -1;
    }
    int need = query(x) + 1;
    int sol = 0;
    int sum = 0;
    for (int b = 20; b >= 0; b--) {
      if (sol + (1 << b) <= n && sum + aib[sol + (1 << b)] < need) {
        sum += aib[sol + (1 << b)];
        sol += (1 << b);
      }
    }
    return sol + 1;
  }
};

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

  cin >> h >> w;
  for (int i = 1; i <= h; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= w; i++) {
    cin >> b[i];
  }
  set<T> s;
  for (int i = 2; i <= h; i++) {
    Fraction fr = {a[i] - a[i - 1], 1};
    s.insert({fr, i, 0});
  }
  for (int i = 2; i <= w; i++) {
    Fraction fr = {b[i] - b[i - 1], 1};
    s.insert({fr, i, 1});
  }
  BIT lines(h), columns(w);
  for (int i = 1; i <= h; i++) {
    lines.update(i, 1);
  }
  for (int i = 1; i <= w; i++) {
    columns.update(i, 1);
  }

  ll ret = 0;
  while (!s.empty()) {
    auto it = s.end();
    it--;
    T aux = *it;
    s.erase(it);
    if (aux.type == 0) {
      int prv = lines.getprev(aux.ind);
      int nxt = lines.getnext(aux.ind);
      Fraction f = aux.val;
      if (prv != -1 && nxt != -1) {
        lines.update(aux.ind, -1);
        Fraction old = {a[nxt] - a[aux.ind], nxt - aux.ind};
        s.erase({old, nxt, 0});
        Fraction fr = {a[nxt] - a[prv], nxt - prv};
        s.insert({fr, nxt, 0});
      } else if (prv != -1 && nxt == -1) {
        lines.update(aux.ind, -1);
        int lastcol = columns.getprev(w + 1);
        ret += (aux.ind - prv) * b[lastcol];
      } else if (prv == -1 && nxt != -1) {
        lines.update(aux.ind, -1);
        int firstcol = columns.getnext(0);
        ret += (nxt - aux.ind) * b[firstcol];
        Fraction old = {a[nxt] - a[aux.ind], nxt - aux.ind};
        s.erase({old, nxt, 0});
      } else {
        break;
      }
    } else {
      int prv = columns.getprev(aux.ind);
      int nxt = columns.getnext(aux.ind);
      Fraction f = aux.val;
      if (prv != -1 && nxt != -1) {
        columns.update(aux.ind, -1);
        Fraction old = {b[nxt] - b[aux.ind], nxt - aux.ind};
        s.erase({old, nxt, 1});
        Fraction fr = {b[nxt] - b[prv], nxt - prv};
        s.insert({fr, nxt, 1});
      } else if (prv != -1 && nxt == -1) {
        columns.update(aux.ind, -1);
        int lastline = lines.getprev(h + 1);
        ret += (aux.ind - prv) * a[lastline];
      } else if (prv == -1 && nxt != -1) {
        columns.update(aux.ind, -1);
        int firstline = lines.getnext(0);
        ret += (nxt - aux.ind) * a[firstline];
        Fraction old = {b[nxt] - b[aux.ind], nxt - aux.ind};
        s.erase({old, nxt, 1});
      } else {
        break;
      }
    }
  }
  cout << ret << "\n";
  return 0;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:171:16: warning: variable 'f' set but not used [-Wunused-but-set-variable]
  171 |       Fraction f = aux.val;
      |                ^
kyoto.cpp:194:16: warning: variable 'f' set but not used [-Wunused-but-set-variable]
  194 |       Fraction f = aux.val;
      |                ^

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60