Submission #483556

#	Time	Username	Problem	Language	Result	Execution time	Memory
483556		macktvz	trapezoid (balkan11_trapezoid)	C++17	5 / 100	131 ms	7944 KiB

trapezoid

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


struct Segment {
    long long ways,num;
};
const int mod = 30013;
Segment join(Segment A, Segment B) {
    Segment ret;
    if (A.num > B.num) return A;
    if (B.num > A.num) return B;
    ret.num = A.num;
    ret.ways = (A.ways+B.ways)%mod;
    return ret;
}

Segment id;

template<class T> struct Seg { // comb(ID,b) = b
	const T ID = id; T comb(T a, T b) { return join(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// min on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};



// keep track of min trap that intersects with curr trap
Seg<Segment> lis;
vector<pair<pair<int,int>,pair<int,int>>> traps;


bool intersect(int i, int j) {
    return (traps[i].second.first > traps[j].first.first || traps[i].second.second > traps[j].first.second);
}



int main() {
    int n; cin >> n;
    int a,b,c,d;
    for(int i = 0; i < n; i++) {
        cin >> a >> b >> c >> d;
        traps.push_back({{a,c},{b,d}});
    }
    lis.init(n+1);
    sort(begin(traps),end(traps));
    Segment f;
    f.num = 1;
    f.ways = 1;
    lis.upd(1,f);
    int ind = 0;
    Segment ret;
    ret.num = 1;
    ret.ways = 1;
    Segment res;
    for(int i = 1; i < n; i++) {
        while (ind != i && !intersect(ind,i)) ind++;
        res = lis.query(1,ind);
        res.num++;
        if (res.ways == 0) res.ways = 1;
        ret = join(ret,res);
        lis.upd(i+1,res);
    }
    cout << ret.num << " " << ret.ways << endl;
}

• Subtask 1: 5 / 100