oj.uz

답안 #536685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
536685 2022-03-13T20:34:19 Z Evang 사다리꼴 (balkan11_trapezoid) C++17
30 / 100
 168 ms 19088 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1e5+5;
const int mod = 30013;
int n;
struct trap {
    int a, b, c, d;
} a[N];
vi qs[N];
struct node {
    int max=0, cnt=0;
} tr[400'005], dp[N];
map<pi, node> mp;

node cmb(node x, node y){
    if(x.max == y.max)
        return node{x.max, (x.cnt+y.cnt)%mod};
    if(x.max > y.max)
        return x;
    return y;
}

void upd(int i, node x){
    i += 2*n;
    tr[i] = cmb(x, tr[i]);

    for(i /= 2; i > 0; i /= 2)
        tr[i] = cmb(tr[2*i], tr[2*i+1]);
}

node qry(int r){
    r += 2*n;
    int l = 2*n;
    node ans;
    while(l<=r){
        if(l&1)
            ans = cmb(ans, tr[l++]);
        if(r&1^1)
            ans = cmb(ans, tr[r--]);
        l /= 2;
        r /= 2;
    }
    return ans;
}

void unik(vi &v){
    sort(all(v));
    vi u{v[0]};
    for(int i = 1; i < ssize(v); ++i)
        if(v[i]^v[i-1])
            u.pb(v[i]);
    swap(u, v);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n;
    vi cct{-inf, inf}, ccb{-inf, inf};
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
        cct.pb(a[i].a);
        cct.pb(a[i].b);
        ccb.pb(a[i].c);
        ccb.pb(a[i].d);
    }
    a[0] = {-inf, -inf, -inf, -inf};
    ++n;
    sort(a, a+n, [](trap x, trap y){
        return x.b < y.b;
    });
    unik(cct);
    unik(ccb);
    for(int i = 0; i < n; ++i){
        a[i].a = lb(all(cct), a[i].a)-cct.begin();
        a[i].b = lb(all(cct), a[i].b)-cct.begin();
        a[i].c = lb(all(ccb), a[i].c)-ccb.begin();
        a[i].d = lb(all(ccb), a[i].d)-ccb.begin();
    }

    int p = 0;
    for(int i = 1; i < n; ++i){
        while(a[p+1].b<a[i].a)
            ++p;
        qs[p].pb(a[i].c-1);
    }

    dp[0] = {0, 1};
    p = 0;
    for(int i = 0; i < n; ++i){
        while(a[p+1].b<a[i].a)
            ++p;

        if(i>0){
            dp[i] = mp[mp(p, a[i].c-1)];
            dp[i].max++;
        }

        upd(a[i].d, dp[i]);
        for(int j: qs[i])
            mp[mp(i, j)] = qry(j);
    }

    node ans = qry(2*n-1);
    cout << ans.max << sp << ans.cnt;
//    cout << dp[n-1].max << sp << dp[n-1].cnt << el;
}

Compilation message

trapezoid.cpp: In function 'node qry(int)':
trapezoid.cpp:97:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   97 |         if(r&1^1)
      |            ~^~

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2772 KB Output isn't correct
4 Correct 3 ms 2776 KB Output is correct
5 Incorrect 5 ms 2976 KB Output isn't correct
6 Incorrect 6 ms 3136 KB Output isn't correct
7 Correct 7 ms 3256 KB Output is correct
8 Incorrect 9 ms 3428 KB Output isn't correct
9 Incorrect 16 ms 4280 KB Output isn't correct
10 Correct 35 ms 5896 KB Output is correct
11 Incorrect 43 ms 6692 KB Output isn't correct
12 Incorrect 74 ms 10900 KB Output isn't correct
13 Incorrect 93 ms 12604 KB Output isn't correct
14 Incorrect 118 ms 14292 KB Output isn't correct
15 Incorrect 149 ms 15076 KB Output isn't correct
16 Incorrect 129 ms 15880 KB Output isn't correct
17 Incorrect 136 ms 16776 KB Output isn't correct
18 Correct 134 ms 17616 KB Output is correct
19 Incorrect 168 ms 17976 KB Output isn't correct
20 Incorrect 162 ms 19088 KB Output isn't correct