oj.uz

Submission #483560

# Submission time Handle Problem Language Result Execution time Memory
483560 2021-10-30T17:10:22 Z macktvz trapezoid (balkan11_trapezoid) C++17
100 / 100
 191 ms 14892 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 6 ms 844 KB Output is correct
8 Correct 9 ms 1088 KB Output is correct
9 Correct 19 ms 1836 KB Output is correct
10 Correct 34 ms 3352 KB Output is correct
11 Correct 44 ms 4044 KB Output is correct
12 Correct 93 ms 7364 KB Output is correct
13 Correct 110 ms 8556 KB Output is correct
14 Correct 132 ms 10872 KB Output is correct
15 Correct 148 ms 11712 KB Output is correct
16 Correct 158 ms 12216 KB Output is correct
17 Correct 171 ms 12948 KB Output is correct
18 Correct 155 ms 13620 KB Output is correct
19 Correct 172 ms 14492 KB Output is correct
20 Correct 191 ms 14892 KB Output is correct