oj.uz

Submission #1101390

# Submission time Handle Problem Language Result Execution time Memory
1101390 2024-10-16T08:01:29 Z NoLove trapezoid (balkan11_trapezoid) C++14
40 / 100
 157 ms 46424 KB 
/**
 *    author : Lăng Trọng Đạt
 *    created: 16-10-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a); (i) <= (b); (i++))
#define FD(i, lo, up) for (int i = (up); (i) >= (lo); i--)
#define si(x) (int)(x.size())
bool mx(int& a, int b) { if (b > a) {a = b; return true;} return false;}
bool mi(int& a, int b) { if (b < a) {a = b; return true;} return false;}
using pii = pair<int, int>;
const int INF = 1e18 + 5;
const int MOD = 1e9 + 7;

const int N = 1e6 + 5;
int g[N];
int n, m, k, q, a, b, c, d;

vector<int> vals = {-1, MOD};

struct Data
{
    vector<int> v;
} t[N];

int res[N];
int bit_max[4*N];
void upd_max(int p, int val) {
    for (; p <= si(vals); p += p & -p) 
        mx(bit_max[p], val);
}
int get_max(int p) {
    int res = 0;
        for (; p > 0; p -= p & -p) 
            mx(res, bit_max[p]);
    return res;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 

    cin >> n;

    vector<array<int, 3>> events;
    FOR(i, 1, n) {
        t[i].v.resize(4);
        for (int& j : t[i].v) {
            cin >> j;
            vals.push_back(j);
        }
        // cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d;
        // vals.push_back(t[i].a); vals.push_back(t[i].b); vals.push_back(t[i].c); vals.push_back(t[i].d);
        events.push_back({t[i].v[0], 0, i});
        events.push_back({t[i].v[1], 1, i});
    }

    sort(all(events));
    sort(all(vals));
    vals.resize(unique(all(vals)) - vals.begin());

    for(auto[x, type, ind] : events) {
        vector<int> v = t[ind].v;
        for (int& i : v) {
            i = lower_bound(all(vals), i) - vals.begin();
        }
        db(x, v[2], v[3])
        if (type == 0) {
            res[ind] = get_max(v[2]) + 1;
        } else {
            upd_max(v[3], res[ind]);
        }
    }

    cout << get_max(si(vals)) << " " << 0;
}

Compilation message

trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:75:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for(auto[x, type, ind] : events) {
      |             ^
trapezoid.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 29008 KB Partially correct
2 Partially correct 7 ms 29008 KB Partially correct
3 Partially correct 5 ms 29264 KB Partially correct
4 Partially correct 5 ms 29264 KB Partially correct
5 Partially correct 7 ms 29520 KB Partially correct
6 Partially correct 8 ms 29776 KB Partially correct
7 Partially correct 9 ms 29776 KB Partially correct
8 Partially correct 11 ms 29912 KB Partially correct
9 Partially correct 20 ms 30596 KB Partially correct
10 Partially correct 28 ms 31860 KB Partially correct
11 Partially correct 40 ms 32884 KB Partially correct
12 Partially correct 72 ms 36968 KB Partially correct
13 Partially correct 91 ms 38484 KB Partially correct
14 Partially correct 108 ms 42480 KB Partially correct
15 Partially correct 118 ms 42328 KB Partially correct
16 Partially correct 135 ms 42840 KB Partially correct
17 Partially correct 138 ms 43572 KB Partially correct
18 Partially correct 112 ms 44960 KB Partially correct
19 Partially correct 138 ms 45864 KB Partially correct
20 Partially correct 157 ms 46424 KB Partially correct