Участник:Ковальков Антон М05-903б/Ada and Species

Материал из DISCOPAL
< Участник:Ковальков Антон М05-903б
Версия от 12:10, 17 декабря 2020; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADACABAA/

Сначала пропробовал, как мне кажется, элегантное решение на Scala. Получилось всего 2 строчки, если не считать чтение из StdIn. Но, к сожалению, оно не проходит по TLE.

object Main extends App {
  import scala.io.StdIn.{readInt, readLine}
 
  implicit class ArrayOps(array: Array[Int]) {
    def >(other: Array[Int]) = (array zip other).foldLeft(true) { case (acc, (x, y)) => acc && x > y }
  }
 
  val vegetables = (1 to readInt).map(_ => readLine.split(" ").map(_.toInt))
  println(vegetables.count(v => !vegetables.exists(x => v > x)))
}

Потом написал другое решение на cpp, с использованием дерева фенвика для функции минимума(лекция про то как оно работает, статья на хабре, пример реализации для одномерного и друмерного случа

Но и тут потерпел неудачу так как двумерное дерево фенвика требует N^2 памяти, а в задаче N ≤ 2*10^5 и Memory limit: 1536MB. Но по сути двумерному дереву нужно только O(log(N)^2)памяти на один запрос.

В результате пришлось реализовывать разряженную структуру данных, которая может хранить и обновлять минимумы в двумерном массиве

CPP14

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
const int MAX_SIZE = 2 * 1e5 + 215;
int N;
 
class Vegetable {
public:
    int a, b, c, d;
 
    Vegetable(int _a, int _b, int _c, int _d) {
        a = _a;
        b = _b;
        c = _c;
        d = _d;
    }
};
 
vector<int> esq[MAX_SIZE], dir[MAX_SIZE], minimuns[MAX_SIZE];
int segIt[MAX_SIZE];
 
void update_sparse(int id, int pos, int left, int right, int x, int delta) {
    if (left == right) {
        minimuns[id][pos] = min(minimuns[id][pos], delta);
        return;
    }
    int mid = (left + right) / 2;
    if (x <= mid) {
        if (esq[id][pos] == -1) {
            esq[id].push_back(-1);
            dir[id].push_back(-1);
            minimuns[id].push_back(MAX_SIZE);
            esq[id][pos] = ++segIt[id];
        }
        update_sparse(id, esq[id][pos], left, mid, x, delta);
    } else {
        if (dir[id][pos] == -1) {
            esq[id].push_back(-1);
            dir[id].push_back(-1);
            minimuns[id].push_back(MAX_SIZE);
            dir[id][pos] = ++segIt[id];
        }
        update_sparse(id, dir[id][pos], mid + 1, right, x, delta);
    }
    int sinistra = (esq[id][pos] == -1) ? MAX_SIZE : minimuns[id][esq[id][pos]];
    int destra = (dir[id][pos] == -1) ? MAX_SIZE : minimuns[id][dir[id][pos]];
    minimuns[id][pos] = min(sinistra, destra);
}
 
void update(int posx, int posy, int delta) {
    while (posx <= N) {
        update_sparse(posx, 0, 1, N, posy, delta);
        posx += (posx & (-posx));
    }
}
 
int get_min_sparse(int id, int pos, int left, int right, int i, int j) {
    if (left > right || left > j || right < i) return MAX_SIZE;
    if (left >= i && right <= j) {
        return minimuns[id][pos];
    }
    int mid = (left + right) / 2;
    int sinistra = (esq[id][pos] == -1) ? MAX_SIZE : get_min_sparse(id, esq[id][pos], left, mid, i, j);
    int destra = (dir[id][pos] == -1) ? MAX_SIZE : get_min_sparse(id, dir[id][pos], mid + 1, right, i, j);
    return min(sinistra, destra);
}
 
int get_min(int posx, int posy) {
    int ans = MAX_SIZE;
    while (posx > 0) {
        ans = min(ans, get_min_sparse(posx, 0, 1, N, 1, posy));
        posx -= (posx & (-posx));
    }
    return ans;
}
 
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        esq[i].push_back(-1);
        dir[i].push_back(-1);
        minimuns[i].push_back(MAX_SIZE);
    }
    vector<Vegetable> vegetables;
    for (int i = 1; i <= N; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vegetables.emplace_back(a, b, c, d);
    }
    sort(vegetables.begin(), vegetables.end(), [](const Vegetable &a, const Vegetable &b) -> bool {
        return a.a < b.a;
    });
 
    int count = 0;
    for (auto vegetable: vegetables) {
        if (get_min(vegetable.b, vegetable.c) > vegetable.d) {
            count++;
            update(vegetable.b, vegetable.c, vegetable.d);
        }
    }
    cout << count;
    return 0;
}


StasFomin 15:10, 17 декабря 2020 (MSK): Ага, жаль, может потом починят TLE. Я учту баллами ваши попытки на других языках!