Submission #935044

#	Time	Username	Problem	Language	Result	Execution time	Memory
935044		sleepntsheep	trapezoid (balkan11_trapezoid)	C++17	100 / 100	139 ms	43584 KiB

trapezoid

#include <iostream>
#include <numeric>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500005

struct A
{
    int hi = -1, freq = 0;

    friend A operator+(A a, A b)
    {
        if (b.hi > a.hi) return b;
        if (a.hi > b.hi) return a;
        return A{a.hi, (a.freq + b.freq) % 30013};
    }

    void operator+=(A a) { *this = *this + a; }
};

int n;
A t[N+5<<1];
array<int, 4> a[N];

int stsz = N;
void upd(int p, A k)
{
    for (t[p += N] += k; p >>= 1;) t[p] = t[p<<1] + t[p<<1|1];
}

A qry(int l, int r)
{
    A z{-1,0};
    for (l += N, r += N; l < r; l >>= 1, r >>= 1)
    {
        if(l&1) z += t[l++];
        if(r&1) z = t[--r] + z;
    }
    return z;
}

vector<int> cx;
A dp[N];
basic_string<int> at_a[N], at_b[N];

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) for (auto &x : a[i]) cin >> x, cx.push_back(x);

    int oo = 1e9+1;
    a[n++] = {oo, oo, oo, oo};
    cx.push_back(-1);
    cx.push_back(oo);

    sort(cx.begin(), cx.end());
    cx.resize(unique(cx.begin(), cx.end()) - cx.begin());

    sort(a, a+n);

    for (int i = 0; i < n; ++i) for (auto &x: a[i]) x = lower_bound(cx.begin(), cx.end(), x) - cx.begin()+1;


    for (int i = 0; i < n; ++i)
        at_a[a[i][0]].push_back(i),
        at_b[a[i][1]].push_back(i);

    upd(0, A{0, 1});

    for (int x = 0; x < N; ++x)
    {
        for (auto i : at_a[x])
        {
            auto [a, b, c, d] = ::a[i];
            dp[i] = qry(0, c);
            dp[i].hi++;
        }

        for (auto i : at_b[x]) upd(a[i][3], dp[i]);
    }

    cout << dp[n-1].hi-1 << ' ' << dp[n-1].freq;

    return 0;
}

Compilation message (stderr)

trapezoid.cpp:35:6: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   35 | A t[N+5<<1];
      |      ^

• Subtask 1: 100 / 100