Submission #328596

#	Time	Username	Problem	Language	Result	Execution time	Memory
328596		Falcon	trapezoid (balkan11_trapezoid)	C++17	100 / 100	194 ms	14444 KiB

trapezoid

#pragma GCC optimize("O2")

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back

#ifdef DEBUG
#define debug(x...) {       ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); }

#define light_debug(x) {    dbg::light = 1; \
                            dbg::dout << __func__ << ":" << __LINE__ << "  " \
                                << #x << " = " << x << endl; \
                            dbg::light = 0; }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

constexpr int MOD{30013};

class segtree {
    using node = pair<int, int>;

    int n;
    vector<node> seg;

private:
    static node comb(const node& a, const node& b) {
        if(a.first == b.first)
            return {a.first, (a.second + b.second) % MOD};
        return a > b ? a : b;
    }

public:
    segtree(int n_) : n{n_}, seg(n << 1) {
        rep(i, n) seg[i + n] = {0, !i};
        rrep(i, n) seg[i] = comb(seg[i << 1], seg[i << 1 | 1]);
    }

    void update(int i, node v) {
        i += n;
        seg[i] = comb(seg[i], v);
        for(i >>= 1; i > 0; i >>= 1)
            seg[i] = comb(seg[i << 1], seg[i << 1 | 1]);
    }

    node query(int y) const {
        node res = {0, 0};
        for(int s = n, e = y + n; s < e; s >>= 1, e >>= 1) {
            if(s & 1) res = comb(res, seg[s++]);
            if(e & 1) res = comb(res, seg[--e]);
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef DEBUG
    freopen("debug", "w", stderr);
    #endif

    struct trapezoid {
        int x1, y1, x2, y2, i;
    };
    
    int n; cin >> n;
    vector<trapezoid> trapezoids(n); 
    for(auto& t : trapezoids)
        cin >> t.x1 >> t.x2 >> t.y1 >> t.y2; 

    int m{};
    {   // Compress y co-ordinates.
        map<int, int> y_vals;
        int i{};
        for(auto& t : trapezoids)
            y_vals[t.y1], y_vals[t.y2], t.i = i++;
        i = 0;
        traverse(y_vals, it) it->second = ++i;
        for(auto& t : trapezoids)
            t.y1 = y_vals[t.y1], t.y2 = y_vals[t.y2];
        m = int(y_vals.size() + 1);
    }

    vector<trapezoid> r_trapezoids{trapezoids};
    sort(all(trapezoids), [&](const trapezoid& a, const trapezoid& b) { return a.x1 < b.x1; });
    sort(all(r_trapezoids), [&](const trapezoid& a, const trapezoid& b) { return a.x2 < b.x2; });

    segtree seg(m);
    vector<pair<int, int>> res(n);

    auto s = r_trapezoids.begin();
    for(auto& t : trapezoids) {
        for(; s != r_trapezoids.end() && s->x2 < t.x1; ++s)
            seg.update(s->y2, res[s->i]);
        res[t.i] = seg.query(t.y1);
        ++res[t.i].first;
        debug(t.i, res[t.i]);
    }

    for(; s != r_trapezoids.end(); ++s)
        seg.update(s->y2, res[s->i]);

    auto ans = seg.query(m);
    cout << ans.first << ' ' << ans.second << '\n';


    #ifdef DEBUG
    dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:32:29: warning: statement has no effect [-Wunused-value]
   32 | #define debug(x...)         42
      |                             ^~
trapezoid.cpp:128:9: note: in expansion of macro 'debug'
  128 |         debug(t.i, res[t.i]);
      |         ^~~~~

• Subtask 1: 100 / 100