제출 #1220892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220892		giorgi123glm	trapezoid (balkan11_trapezoid)	C++20	40 / 100	303 ms	27144 KiB

trapezoid

#include <bitset>
#include <functional>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;

template <typename T>
class segment_tree {
    public:
        int siz = 1;
        vector <T> segtree;
        function <T(T, T)> merge;
        
        segment_tree(function <T(T, T)> IN) : merge (IN) {}

        void resize (int n) {
            while (siz < n)
                siz *= 2;
            segtree.resize (2 * siz);
        }

        void update (int ind, T K) {
            int u = siz + ind - 1;
            segtree[u] = merge (segtree[u], K);
            u /= 2;
            while (u)
                segtree[u] = merge (
                    segtree[2 * u], segtree[2 * u + 1]
                ), u /= 2;
        }

        T get (int L, int R, int u, int l, int r) {
            if (r < L || R < l)
                return T();

            if (L <= l && r <= R)
                return segtree[u];

            const int m = (l + r) / 2;
            return merge (
                get (L, R, 2 * u, l, m),
                get (L, R, 2 * u + 1, m + 1, r)
            );
        }

        T get (int L, int R) {
            return get (L, R, 1, 1, siz);
        }
};

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

    const int lim = 4e5 + 20;

    int N = 0;
    cin >> N;

    vector <array <int, 4> > v (N + 1);
    for (int i = 1; i <= N; i++)
        cin >> v[i][0] >> v[i][1] >> v[i][2] >> v[i][3];

    [&]()->void {
        map <int, int> m;
        for (array <int, 4>& e : v)
            m[e[0]] = 0, m[e[1]] = 0, m[e[2]] = 0, m[e[3]] = 0;
        int free = 0;
        for (pair <const int, int>& e : m)
            e.second = ++free;
        for (array <int, 4>& e : v) {
            e[0] = m[e[0]];
            e[1] = m[e[1]];
            e[2] = m[e[2]];
            e[3] = m[e[3]];
        }
    }();

    vector <array <int, 4> > byFirst (lim + 1);
    for (int i = 1; i <= N; i++)
        byFirst[v[i][0]] = v[i];

    segment_tree <int> segtree (
        [](int a, int b) {
            return max (a, b);
        }
    );
    segtree.resize (lim + 1);

    vector <vector <pair <int, int> > > tasks (lim + 1);

    for (int i = 1; i <= lim; i++) {
        for (pair <int, int>& e : tasks[i])
            segtree.update (e.first, e.second);
        if (byFirst[i][0] == i) {
            int curans = segtree.get (1, byFirst[i][2]) + 1;
            tasks[byFirst[i][1]].emplace_back (byFirst[i][3], curans);
        }
    }

    cout << segtree.get (1, lim) << ' ' << 0 << '\n';
}

• Subtask 1: 40 / 100