제출 #483560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483560		macktvz	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	191 ms	14892 KiB

trapezoid

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

#define f first
#define s second

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;




vector<pair<int,pair<int,int>>> top;
vector<pair<int,int>> bot;

vector<int> bo;

int index(int y) {return lower_bound(begin(bo),end(bo),y)-begin(bo); }

int main() {
    id.num = 0;
    id.ways = 0;
    int n; cin >> n;
    int a,b,c,d;
    lis.init(2*n+1);
    for(int i = 0; i < n; i++) {
        cin >> a >> b >> c >> d;
        top.push_back({a,{i,1}});
        top.push_back({b,{i,-1}});
        bot.push_back({c,d});
        bo.push_back(c);
        bo.push_back(d);
    }
    sort(begin(bo),end(bo));
    sort(begin(top),end(top));
    Segment ans[2*n];
    Segment ret;
    Segment res;
    ret.ways = 0;
    ret.num = 0;
    for(int i = 0; i < 2*n; i++) {
        if (top[i].s.s == 1) {
            res = lis.query(1,index(bot[top[i].s.f].f)+1);
            res.num++;
            if(res.ways == 0) res.ways = 1;
            ans[top[i].s.f] = res;
            ret = join(ret,res);
        } else {
            lis.upd(index(bot[top[i].s.f].s)+1,ans[top[i].s.f]);
        }
    }
    cout << ret.num << " " << ret.ways << endl;
}

• Subtask 1: 100 / 100