oj.uz

Submission #1108138

# Submission time Handle Problem Language Result Execution time Memory
1108138 2024-11-03T01:27:39 Z Zero_OP trapezoid (balkan11_trapezoid) C++14
100 / 100
 74 ms 8172 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 396 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 4 ms 848 KB Output is correct
9 Correct 7 ms 1104 KB Output is correct
10 Correct 13 ms 1868 KB Output is correct
11 Correct 18 ms 1868 KB Output is correct
12 Correct 36 ms 4168 KB Output is correct
13 Correct 42 ms 4420 KB Output is correct
14 Correct 66 ms 8044 KB Output is correct
15 Correct 53 ms 8004 KB Output is correct
16 Correct 58 ms 8016 KB Output is correct
17 Correct 60 ms 8004 KB Output is correct
18 Correct 53 ms 8004 KB Output is correct
19 Correct 63 ms 8004 KB Output is correct
20 Correct 74 ms 8172 KB Output is correct