Submission #1172936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172936		nguyenkhangninh99	사다리꼴 (balkan11_trapezoid)	C++17	40 / 100	141 ms	13364 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 2e6 + 5;

int st[4 * maxn];

void update(int id, int l, int r, int pos, int val){
    if(l > pos || r < pos || l > r) return;

    if(l == r){
        st[id] = max(st[id], val);
        return;
    }   

    int mid = (l + r) / 2;

    update(id * 2, l, mid, pos, val);
    update(id * 2 + 1, mid + 1, r, pos, val);

    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v){
    if(r < u || l > v || l > r) return 0;

    if(u <= l && r <= v) return st[id];

    int mid = (l + r) / 2;

    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
void solve(){
    int k; cin >> k;

    vector<array<int, 4>> v;
    vector<int> comp1, comp2, a(k + 1), b(k + 1), c(k + 1), d(k + 1);

    for(int i = 1; i <= k; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        comp1.push_back(a[i]);
        comp1.push_back(b[i]);
        comp2.push_back(c[i]);
        comp2.push_back(d[i]);
    }

    sort(comp1.begin(), comp1.end());
    sort(comp2.begin(), comp2.end());
    comp1.erase(unique(comp1.begin(), comp1.end()), comp1.end());
    comp2.erase(unique(comp2.begin(), comp2.end()), comp2.end());

    //a tăng dần, b tăng dần, c tăng dần, d tăng dần

    for(int i = 1; i <= k; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        int aa = lower_bound(comp1.begin(), comp1.end(), a[i]) - comp1.begin();
        int bb = lower_bound(comp1.begin(), comp1.end(), b[i]) - comp1.begin();
        int cc = lower_bound(comp2.begin(), comp2.end(), c[i]) - comp2.begin();
        int dd = lower_bound(comp2.begin(), comp2.end(), d[i]) - comp2.begin();
        v.push_back({aa, bb, cc, dd});
    }

    sort(v.begin(), v.end());

    multiset<array<int, 3>> s;

    int res = 0;

    for(int i = 0; i < k; i++){
        while(!s.empty() && (*s.begin())[0] < v[i][0]){
            update(1, 1, 2000000, (*s.begin())[1], (*s.begin())[2]);
            s.erase(s.begin());
        }
        int x = get(1, 1, 2000000, 1, v[i][2] - 1) + 1;
        res = max(res, x);
        s.insert({v[i][1], v[i][3], x});
    }

    cout << res << " " << 69420;

}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

• Subtask 1: 40 / 100