Submission #1211471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211471		vanea	trapezoid (balkan11_trapezoid)	C++20	22 / 100	120 ms	9228 KiB

trapezoid

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

const int mxN = 1e5+10;

vector<int> values;
int st[4*mxN], ans[mxN];

int val(int x) {
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}

void upd(int node, int l, int r, int k, int x) {
    if(l == r && l == k) {
        st[node] = x;
        return ;
    }
    if(l > k || r < k) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, k, x);
    upd(node*2+1, mid+1, r, k, x);
    st[node] = max(st[node*2], st[node*2+1]);
}

int qry(int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[node];
    if(l1 > r || r1 < l) return 0;
    int mid = (l+r)/2;
    return max(qry(node*2, l, mid, l1, r1), qry(node*2+1, mid+1, r, l1, r1));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    vector<array<int, 4>> events;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        events.push_back({a, c, 1, i});
        events.push_back({b, d, -1, i});
        values.push_back(a); values.push_back(c);
        values.push_back(b); values.push_back(d);
    }
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    sort(events.begin(), events.end());
    int mx = 0;
    for(auto &[x, y, flag, idx] : events) {
        x = val(x); y = val(y);
        if(flag == 1) {
            ans[idx] = 1+qry(1, 0, values.size()+1, 0, y);
            mx = max(mx, ans[idx]);
        }
        else {
            upd(1, 0, values.size()+1, y, ans[idx]);
        }
    }
    cout << mx << ' ' << 0;
}

• Subtask 1: 22 / 100