Submission #1110416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110416		_callmelucian	trapezoid (balkan11_trapezoid)	C++14	100 / 100	98 ms	12480 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const int MOD = 30013;

int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }

struct getMax {
    int best, cnt;

    getMax() : best(0), cnt(0) {}
    getMax (int a, int b) : best(a), cnt(b) {}

    void push (int cur) {
        if (cur > best) best = cur, cnt = 1;
        else if (cur == best) cnt = add(cnt, 1);
    }

    getMax operator + (const getMax &o) const {
        if (best == o.best) return getMax(best, add(cnt, o.cnt));
        return (best > o.best ? *this : o);
    }
};

struct IT {
    vector<getMax> tr;
    IT (int sz) : tr(4 * sz) {}

    void update (int pos, getMax val, int k, int l, int r) {
        for (; l < r;) {
            int mid = (l + r) >> 1;
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
        }
        tr[k] = tr[k] + val;
        for (k /= 2; k; k /= 2)
            tr[k] = tr[2 * k] + tr[2 * k + 1];
    }

    getMax query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return getMax();
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return query(a, b, 2 * k, l, mid) + query(a, b, 2 * k + 1, mid + 1, r);
    }
};

struct item {
    int a, b, c, d;

    item() : a(a), b(b), c(c), d(d) {}
    item (int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {}

    bool operator < (const item &o) const { return a < o.a; }

    friend istream& operator >> (istream &inp, item &i) {
        return inp >> i.a >> i.b >> i.c >> i.d, inp;
    }
} trapezoid[mn];

vector<int> cmp;
getMax dp[mn];

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

    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> trapezoid[i];
        cmp.push_back(trapezoid[i].c), cmp.push_back(trapezoid[i].d);
    }
    sort(trapezoid, trapezoid + n);
    sort(all(cmp)), filter(cmp);

    for (int i = 0; i < n; i++) {
        trapezoid[i].c = lower_bound(all(cmp), trapezoid[i].c) - cmp.begin();
        trapezoid[i].d = lower_bound(all(cmp), trapezoid[i].d) - cmp.begin();
    }

    priority_queue<pii> wait;
    IT tree(cmp.size());
    for (int i = 0; i < n; i++) {
        while (wait.size() && -wait.top().first < trapezoid[i].a) {
            int j = wait.top().second; wait.pop();
            tree.update(trapezoid[j].d, dp[j], 1, 0, cmp.size() - 1);
        }
        dp[i] = tree.query(0, trapezoid[i].c - 1, 1, 0, cmp.size() - 1);
        dp[i].best++, dp[i].push(1);

        wait.emplace(-trapezoid[i].b, i);
    }

    getMax ans;
    for (int i = 0; i < n; i++) ans = ans + dp[i];
    cout << ans.best << " " << ans.cnt << "\n";

    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In constructor 'item::item()':
trapezoid.cpp:61:5: warning: 'item::a' is initialized with itself [-Winit-self]
   61 |     item() : a(a), b(b), c(c), d(d) {}
      |     ^~~~
trapezoid.cpp:61:5: warning: 'item::b' is initialized with itself [-Winit-self]
trapezoid.cpp:61:5: warning: 'item::c' is initialized with itself [-Winit-self]
trapezoid.cpp:61:5: warning: 'item::d' is initialized with itself [-Winit-self]
trapezoid.cpp: In constructor 'item::item()':
trapezoid.cpp:61:16: warning: '*<unknown>.item::a' is used uninitialized in this function [-Wuninitialized]
   61 |     item() : a(a), b(b), c(c), d(d) {}
      |                ^
trapezoid.cpp:61:22: warning: '*<unknown>.item::b' is used uninitialized in this function [-Wuninitialized]
   61 |     item() : a(a), b(b), c(c), d(d) {}
      |                      ^
trapezoid.cpp:61:28: warning: '*<unknown>.item::c' is used uninitialized in this function [-Wuninitialized]
   61 |     item() : a(a), b(b), c(c), d(d) {}
      |                            ^
trapezoid.cpp:61:34: warning: '*<unknown>.item::d' is used uninitialized in this function [-Wuninitialized]
   61 |     item() : a(a), b(b), c(c), d(d) {}
      |                                  ^

• Subtask 1: 100 / 100