Submission #1172939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172939		nguyenkhangninh99	trapezoid (balkan11_trapezoid)	C++17	100 / 100	164 ms	44520 KiB

trapezoid

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

#define int long long

const int maxn = 2e6 + 5, mod = 30013;

pair<int, int> st[4 * maxn];

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    if(a.first == 0) return b;
    if(b.first == 0) return a;
    if(a.first == b .first) return {a.first, (a.second + b.second) % mod};
    else return max(a, b);
}
void update(int id, int l, int r, int pos, pair<int, int> val){
    if(l > pos || r < pos || l > r) return;

    if(l == r){
        st[id] = merge(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] = merge(st[id * 2], st[id * 2 + 1]);
}

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

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

    int mid = (l + r) / 2;

    return merge(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, 4>> s;

    int res = 0, cnt = 0;

    for(int i = 0; i < k; i++){
        while(!s.empty() && (*s.begin())[0] < v[i][0]){
            update(1, 1, 2000000, (*s.begin())[1], pair<int, int>{(*s.begin())[2], (*s.begin())[3]});
            s.erase(s.begin());
        }
        pair<int, int> x = get(1, 1, 2000000, 1, v[i][2] - 1);
        x.first++;
        if(x.first > res){
            res = x.first;
            cnt = x.second;
        }else if(x.first == res) (cnt += x.second) %= mod;
        s.insert({v[i][1], v[i][3], x.first, x.second});
    }

    cout << res << " " << cnt;

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

    for(int i = 1; i < maxn; i++) st[i].second = 1;

    solve();
}

• Subtask 1: 100 / 100