oj.uz

Submission #787202

# Submission time Handle Problem Language Result Execution time Memory
787202 2023-07-18T22:57:00 Z tvladm2009 Sightseeing in Kyoto (JOI22_kyoto) C++17
100 / 100
 419 ms 19700 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 464 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 328 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 110 ms 8320 KB Output is correct
5 Correct 58 ms 7636 KB Output is correct
6 Correct 38 ms 3540 KB Output is correct
7 Correct 350 ms 19572 KB Output is correct
8 Correct 361 ms 19620 KB Output is correct
9 Correct 358 ms 19544 KB Output is correct
10 Correct 379 ms 19616 KB Output is correct
11 Correct 130 ms 19620 KB Output is correct
12 Correct 339 ms 19620 KB Output is correct
13 Correct 363 ms 19620 KB Output is correct
14 Correct 170 ms 19552 KB Output is correct
15 Correct 80 ms 19532 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 464 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 0 ms 328 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 324 KB Output is correct
30 Correct 0 ms 324 KB Output is correct
31 Correct 2 ms 468 KB Output is correct
32 Correct 110 ms 8320 KB Output is correct
33 Correct 58 ms 7636 KB Output is correct
34 Correct 38 ms 3540 KB Output is correct
35 Correct 350 ms 19572 KB Output is correct
36 Correct 361 ms 19620 KB Output is correct
37 Correct 358 ms 19544 KB Output is correct
38 Correct 379 ms 19616 KB Output is correct
39 Correct 130 ms 19620 KB Output is correct
40 Correct 339 ms 19620 KB Output is correct
41 Correct 363 ms 19620 KB Output is correct
42 Correct 170 ms 19552 KB Output is correct
43 Correct 80 ms 19532 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 0 ms 332 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 0 ms 212 KB Output is correct
55 Correct 118 ms 9108 KB Output is correct
56 Correct 2 ms 468 KB Output is correct
57 Correct 9 ms 1268 KB Output is correct
58 Correct 30 ms 3028 KB Output is correct
59 Correct 375 ms 19700 KB Output is correct
60 Correct 379 ms 19620 KB Output is correct
61 Correct 381 ms 19616 KB Output is correct
62 Correct 368 ms 19528 KB Output is correct
63 Correct 134 ms 19660 KB Output is correct
64 Correct 365 ms 19576 KB Output is correct
65 Correct 419 ms 19584 KB Output is correct
66 Correct 171 ms 19620 KB Output is correct
67 Correct 87 ms 19604 KB Output is correct