Submission #483558

#	Time	Username	Problem	Language	Result	Execution time	Memory
483558		macktvz	trapezoid (balkan11_trapezoid)	C++17	5 / 100	127 ms	5028 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;


struct Trapezoid {
    int a,b,c,d;
    const bool operator<(const Trapezoid& o) const { 
        if(b < o.a & d < o.c) return 1;
        return a < o.a;
    }
};
vector<Trapezoid> traps;

bool intersect(int i, int j) {
    return (traps[i].b > traps[j].a || traps[i].d > traps[j].c);
}



int main() {
    int n; cin >> n;
    Trapezoid t;
    for(int i = 0; i < n; i++) {
        cin >> t.a >> t.b >> t.c >> t.d;
        traps.push_back(t);
    }
    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;
}

Compilation message (stderr)

trapezoid.cpp: In member function 'const bool Trapezoid::operator<(const Trapezoid&) const':
trapezoid.cpp:48:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   48 |         if(b < o.a & d < o.c) return 1;
      |            ~~^~~~~

• Subtask 1: 5 / 100