oj.uz

답안 #483558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483558 2021-10-30T16:45:47 Z macktvz 사다리꼴 (balkan11_trapezoid) C++17
5 / 100
 127 ms 5028 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;


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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Incorrect 2 ms 332 KB Output isn't correct
5 Incorrect 3 ms 332 KB Output isn't correct
6 Incorrect 4 ms 460 KB Output isn't correct
7 Incorrect 5 ms 460 KB Output isn't correct
8 Incorrect 6 ms 648 KB Output isn't correct
9 Incorrect 12 ms 904 KB Output isn't correct
10 Incorrect 26 ms 1252 KB Output isn't correct
11 Incorrect 31 ms 1468 KB Output isn't correct
12 Incorrect 65 ms 2740 KB Output isn't correct
13 Incorrect 86 ms 3260 KB Output isn't correct
14 Incorrect 94 ms 3636 KB Output isn't correct
15 Incorrect 95 ms 3824 KB Output isn't correct
16 Incorrect 102 ms 4148 KB Output isn't correct
17 Incorrect 116 ms 4388 KB Output isn't correct
18 Incorrect 124 ms 4644 KB Output isn't correct
19 Incorrect 122 ms 4868 KB Output isn't correct
20 Incorrect 127 ms 5028 KB Output isn't correct