Submission #1033219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033219		raphaelp	trapezoid (balkan11_trapezoid)	C++14	100 / 100	334 ms	50792 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
    vector<long long> st, count;
    long long N;
    long long l(long long x) { return (x << 1); }
    long long r(long long x) { return (x << 1) + 1; }
    void update(long long L, long long R, long long a, long long val, long long c, long long x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            st[x] = val;
            count[x] = c;
        }
        else
        {
            long long m = (L + R) / 2;
            update(L, m, a, val, c, l(x));
            update(m + 1, R, a, val, c, r(x));
            st[x] = max(st[l(x)], st[r(x)]);
            count[x] = ((st[l(x)] == st[x]) ? count[l(x)] : 0) + ((st[r(x)] == st[x]) ? count[r(x)] : 0);
        }
    }
    pair<long long, long long> RSQ(long long L, long long R, long long a, long long b, long long x)
    {
        if (L > b || R < a)
            return {0, 0};
        if (L >= a && R <= b)
            return {st[x], count[x]};
        long long m = (L + R) / 2;
        pair<long long, long long> temp1 = RSQ(L, m, a, b, l(x)), temp2 = RSQ(m + 1, R, a, b, r(x));
        if (temp1.first < temp2.first)
            swap(temp1, temp2);
        if (temp1.first == temp2.first)
            temp1.second += temp2.second;
        return temp1;
    }

public:
    SegTree(long long x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 0);
        count.assign(2 * N, 0);
    }
    void update(long long x, long long val, long long c) { update(0, N - 1, x, val, c, 1); }
    pair<long long, long long> RSQ(long long a, long long b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
    long long N;
    cin >> N;
    vector<vector<long long>> Tab;
    vector<long long> vals;
    for (long long i = 0; i < N; i++)
    {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        vals.push_back(a), vals.push_back(b), vals.push_back(c), vals.push_back(d);
        Tab.push_back({a, c, b, d});
    }
    sort(vals.begin(), vals.end());
    sort(Tab.begin(), Tab.end());
    map<long long, long long> M;
    for (long long i = 0; i < vals.size(); i++)
    {
        M[vals[i]] = i;
    }
    for (long long i = 0; i < N; i++)
    {
        for (long long j = 0; j < 4; j++)
            Tab[i][j] = M[Tab[i][j]];
    }
    SegTree ST(4 * N);
    priority_queue<vector<long long>> PQ;
    vector<pair<long long, long long>> ans(N);
    pair<long long, long long> ans2 = {0, 0};
    for (long long i = 0; i < N; i++)
    {
        while (!PQ.empty() && -PQ.top()[0] < Tab[i][0])
        {
            ST.update(PQ.top()[1], PQ.top()[2], PQ.top()[3]);
            PQ.pop();
        }
        ans[i] = ST.RSQ(0, Tab[i][1]);
        ans[i].first++;
        if (ans[i].first == 1)
            ans[i].second++;
        ans[i].second = ans[i].second % 30013;
        PQ.push({-Tab[i][2], Tab[i][3], ans[i].first, ans[i].second});
        if (ans[i].first > ans2.first)
            ans2 = {ans[i].first, 0};
        if (ans[i].first == ans2.first)
            ans2.second += ans[i].second;
        ans2.second = ans2.second % 30013;
    }
    cout << ans2.first << ' ' << ans2.second;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:69:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (long long i = 0; i < vals.size(); i++)
      |                           ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100