Submission #1108138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108138		Zero_OP	trapezoid (balkan11_trapezoid)	C++14	100 / 100	74 ms	8172 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int mod = 30013;

void add(int& x, int y){
    x += y;
    if(x >= mod) x -= mod;
}

struct Node{
    int mx, ways;
    Node(int mx = 0, int ways = 0) : mx(mx), ways(ways) {}

    friend Node operator + (const Node& a, const Node& b){
        Node c(max(a.mx, b.mx), 0);
        if(a.mx == c.mx) add(c.ways, a.ways);
        if(b.mx == c.mx) add(c.ways, b.ways);
        return c;
    }

    Node& operator += (const Node& oth){
        if(mx == oth.mx) add(ways, oth.ways);
        else if(mx < oth.mx) mx = oth.mx, ways = oth.ways;
        return *this;
    }
};

struct Fenwick{
    vector<Node> bit;
    Fenwick(int n) : bit(n + 1, Node(0, 0)) {}

    void update(int id, Node v){
        assert(id > 0);
        for(; id < (int)bit.size(); id += id & (-id)){
            bit[id] += v;
        }
    }

    Node query(int id){
        Node ret(0, 0);
        assert(id < (int)bit.size());
        for(; id > 0; id -= id & (-id)){
            ret += bit[id];
        }
        return ret;
    }
};

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N;
    cin >> N;

    vector<int> v;
    vector<tuple<int, int, int, int>> E;
    for(int i = 0; i < N; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        v.emplace_back(c);
        v.emplace_back(d);
        E.emplace_back(a, 0, c, i);
        E.emplace_back(b, 1, d, i);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    sort(E.begin(), E.end());

    auto findPos = [&](int i){
        return lower_bound(v.begin(), v.end(), i) - v.begin() + 1;
    };

    for(auto& [x, type, pos, id] : E){
        pos = findPos(pos);
    }

    Fenwick ft((int)v.size());
    Node res(0, 0);
    vector<Node> f(N, Node(0, 0));
    for(auto [x, type, pos, id] : E){
        if(type == 0){
            Node cur = ft.query(pos);
            if(cur.mx == 0) {
                cur = Node(1, 1);
            } else{
                ++cur.mx;
            }

            f[id] = cur;
        } else{
            ft.update(pos, f[id]);
        }
    }

    for(int i = 0; i < N; ++i){
        res += f[i];
    }

    cout << res.mx << ' ' << res.ways << '\n';

    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for(auto& [x, type, pos, id] : E){
      |               ^
trapezoid.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for(auto [x, type, pos, id] : E){
      |              ^

• Subtask 1: 100 / 100