oj.uz

답안 #483556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483556 2021-10-30T16:11:29 Z macktvz 사다리꼴 (balkan11_trapezoid) C++17
5 / 100
 131 ms 7944 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 292 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Incorrect 2 ms 300 KB Output isn't correct
5 Incorrect 3 ms 460 KB Output isn't correct
6 Incorrect 6 ms 460 KB Output isn't correct
7 Incorrect 6 ms 588 KB Output isn't correct
8 Incorrect 6 ms 716 KB Output isn't correct
9 Incorrect 12 ms 1096 KB Output isn't correct
10 Incorrect 26 ms 1804 KB Output isn't correct
11 Incorrect 31 ms 2252 KB Output isn't correct
12 Incorrect 64 ms 4032 KB Output isn't correct
13 Incorrect 77 ms 4760 KB Output isn't correct
14 Incorrect 92 ms 5624 KB Output isn't correct
15 Incorrect 99 ms 5808 KB Output isn't correct
16 Incorrect 106 ms 6308 KB Output isn't correct
17 Incorrect 110 ms 6692 KB Output isn't correct
18 Incorrect 112 ms 6944 KB Output isn't correct
19 Incorrect 124 ms 7452 KB Output isn't correct
20 Incorrect 131 ms 7944 KB Output isn't correct