oj.uz

답안 #1003993

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003993 2024-06-20T21:57:46 Z whatthemomooofun1729 사다리꼴 (balkan11_trapezoid) C++17
46 / 100
 171 ms 29524 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <sstream>
#include <chrono>
#include <random>

#define ff first
#define ss second
#define PB push_back
#define sz(x) int(x.size())
#define rsz resize
#define fch(xxx, yyy) for (auto xxx : yyy) // abusive notation
#define all(x) (x).begin(),(x).end()
#define eps 1e-9

// more abusive notation (use at your own risk):
// #define int ll

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

// debugging
void __print(int x) {std::cerr << x;}
void __print(ll x) {std::cerr << x;} /* remember to uncomment this when not using THE MACRO */
void __print(unsigned x) {std::cerr << x;}
void __print(ull x) {std::cerr << x;}
void __print(float x) {std::cerr << x;}
void __print(double x) {std::cerr << x;}
void __print(ld x) {std::cerr << x;}
void __print(char x) {std::cerr << '\'' << x << '\'';}
void __print(const char *x) {std::cerr << '\"' << x << '\"';}
void __print(const string& x) {std::cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {std::cerr << '{'; __print(x.ff); std::cerr << ", "; __print(x.ss); std::cerr << '}';}
template<typename T> void __print(const T& x) {int f = 0; std::cerr << '{'; for (auto &i: x) std::cerr << (f++ ? ", " : ""), __print(i); std::cerr << "}";}
void _print() {std::cerr << "]\n";}
template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...);}
void println() {std::cerr << ">--------------------<" << endl;}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// templates
template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;}
template <class T> using gr = greater<T>;
template <class T> using vc = vector<T>;
template <class T> using p_q = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>;
template <class T1, class T2> using pr = pair<T1, T2>;
mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count());
int rng(int M) {return (int)(rng_ll()%M);} /*returns any random number in [0, M) */

// const variables
constexpr int INF = (int)2e9;
constexpr int MOD = 998244353;
constexpr ll LL_INF = (ll)3e18;
constexpr int mod = (int)1e9 + 7;
constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7

void setIO(const string& str) {// fast input/output
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (str.empty()) return;
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}

void chkmax(pii& p, pii q) {
    if (p.ff < q.ff) p = q;
    else if (p.ff == q.ff && p.ff != 0) {
        p.ss += q.ss;
    }
}

template<class T> struct BIT {
    // Fenwick Tree, 0-based indexing
    int N;
    vector<T> a, bit;
    BIT(int n) {
        n++; // in case we call bit[i].set(N) (could lead to out of bounds error)
        N = n;
        a.clear(), bit.clear();
        a.rsz(n, {0, 1}), bit.rsz(n, {0, 1});
    }
    T prefix_sum(int r) {
        if (r < 0) return {0, 1};
        T ret = {0, 1};
        for (; r >= 0; r = (r & (r+1))-1) chkmax(ret, bit[r]);
        return ret;
    }
    void add(int i, T d) {
        chkmax(a[i], d);
        for (; i < N; i = i | (i+1)) chkmax(bit[i], d);
    }
};

int N, B, T;
vc<pii> top, bottom;
vi a, b, c, d;
vc<pii> dp;

signed main() { // TIME YOURSELF !!!
    setIO("");
    cin >> N;
    a.rsz(N), b.rsz(N), c.rsz(N), d.rsz(N);
    set<pii> tp, bt;
    for (int i = 0; i < N; ++i) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        tp.insert({a[i], i});
        tp.insert({b[i], i});
        bt.insert({c[i], i});
        bt.insert({d[i], i});
    }
    top = vc<pii>(all(tp));
    bottom = vc<pii>(all(bt));
    B = sz(bottom), T = sz(top);
    dp.rsz(T, {0, 1});
    BIT<pii> butt = BIT<pii>(B);
    for (int i = 0; i < sz(top); ++i) {
        if (top[i].ff == a[top[i].ss]) {
            int k = int(lower_bound(all(bottom), pii{c[top[i].ss], -INF}) - bottom.begin());
            pii thingy = butt.prefix_sum(k - 1);
            dp[i] = {thingy.ff + 1, thingy.ss};
        } else if (top[i].ff == b[top[i].ss]) {
            int j = int(lower_bound(all(top), pii{a[top[i].ss], -INF}) - top.begin());
            int k = int(lower_bound(all(bottom), pii{d[top[i].ss], -INF}) - bottom.begin());
            butt.add(k, dp[j]);
        }
    }
    pii res = {0, 1};
    for (int i = 0; i < N; ++i) {
        int j = int(lower_bound(all(top), pii{a[i], -INF}) - top.begin());
        chkmax(res, dp[j]);
    }
    cout << res.ff << ' ' << res.ss;
    return 0;
}

// TLE -> TRY NOT USING DEFINE INT LONG LONG
// CE -> CHECK LINE 45
// 5000 * 5000 size matrices are kinda big (potential mle)
// Do something, start simpler

Compilation message

trapezoid.cpp: In function 'void setIO(const string&)':
trapezoid.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 1 ms 604 KB Partially correct
4 Partially correct 1 ms 604 KB Partially correct
5 Partially correct 2 ms 856 KB Partially correct
6 Partially correct 3 ms 1116 KB Partially correct
7 Partially correct 4 ms 1396 KB Partially correct
8 Partially correct 7 ms 1884 KB Partially correct
9 Partially correct 15 ms 3420 KB Partially correct
10 Partially correct 26 ms 6492 KB Partially correct
11 Partially correct 35 ms 7844 KB Partially correct
12 Partially correct 67 ms 15700 KB Partially correct
13 Partially correct 88 ms 17832 KB Partially correct
14 Partially correct 116 ms 21324 KB Partially correct
15 Partially correct 120 ms 22328 KB Partially correct
16 Partially correct 140 ms 23124 KB Partially correct
17 Partially correct 143 ms 25688 KB Partially correct
18 Partially correct 121 ms 25688 KB Partially correct
19 Partially correct 141 ms 27220 KB Partially correct
20 Partially correct 171 ms 29524 KB Partially correct