Submission #889701

#	Time	Username	Problem	Language	Result	Execution time	Memory
889701		chanhchuong123	trapezoid (balkan11_trapezoid)	C++14	100 / 100	74 ms	9472 KiB

trapezoid

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

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

const int MAX = 100010;
const int MOD = 30013;
int nArr;
vector<int> tmp;
pair<int, int> ans[MAX];
pair<int, int> bit[MAX << 1];
vector<tuple<int, int, int>> events;

void add(int &x, const int &y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

void update(int id, pair<int, int> value) {
    for (; id <= 2 * nArr; id += id & -id) {
        if (bit[id].fi <  value.fi) {
            bit[id] = value;
            continue;
        }
        if (bit[id].fi == value.fi)
            add(bit[id].se, value.se);
    }
}

pair<int, int> get(int id) {
    pair<int, int> res = make_pair(0, 1);
    for (; id > 0; id -= id & -id) {
        if (res.fi <  bit[id].fi) {
            res = bit[id];
            continue;
        }
        if (res.fi == bit[id].fi)
            add(res.se, bit[id].se);
    }
    return res;
}

void init(void) {
    cin >> nArr;
    for (int i = 1; i <= nArr; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        events.emplace_back(a, -i, c);
        events.emplace_back(b, +i, d);
        tmp.push_back(c);
        tmp.push_back(d);
    }
    sort(all(tmp)); tmp.resize(unique(all(tmp)) - tmp.begin());
}

#define POS(value) (upper_bound(all(tmp), value) - tmp.begin())
void process(void) {
    sort(all(events));
    for (tuple<int, int, int> &e: events) {
        int x, y, i; tie(x, i, y) = e;
        int id = abs(i);
        y = POS(y);

        if (i < 0) {
            ans[id] = get(y - 1);
            ans[id].fi += 1;
            continue;
        }

        update(y, ans[id]);
    }

    pair<int, int> res = get(2 * nArr);
    cout << res.fi << ' ' << res.se;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//	freopen(".INP", "r",  stdin);
//	freopen(".OUT", "w", stdout);

    init();
    process();

	return 0;
}

• Subtask 1: 100 / 100