Submission #136174

#	Time	Username	Problem	Language	Result	Execution time	Memory
136174		jovan_b	trapezoid (balkan11_trapezoid)	C++17	90 / 100	514 ms	31456 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MOD = 30013;

int a[100005], b[100005], c[100005], d[100005];
map <int, int> u;

pair <int, int> niz[200005];

int dp[100005];
int brn[100005];

struct drvo{
    int val;
    int br;
} seg[1000000];

void upd(int node, int l, int r, int x, int val){
    if(l > x || r < x) return;
    if(l == r){
        seg[node].val = dp[val];
        seg[node].br = brn[val];
        seg[node].br %= MOD;
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, x, val);
    upd(node*2+1, mid+1, r, x, val);
    seg[node].val = max(seg[node*2].val, seg[node*2+1].val);
    seg[node].br = 0;
    if(seg[node].val == seg[node*2].val){
        seg[node].br += seg[node*2].br;
    }
    if(seg[node].val == seg[node*2+1].val){
        seg[node].br += seg[node*2+1].br;
    }
    seg[node].br %= MOD;
}

pair <int, int> query(int node, int l, int r, int tl, int tr){
    if(l > tr || tl > r) return {0, 1};
    if(tl <= l && r <= tr){
        return {seg[node].val, seg[node].br};
    }
    int mid = (l+r)/2;
    pair <int, int> a1  = query(node*2, l, mid, tl, tr);
    pair <int, int> b1 = query(node*2+1, mid+1, r, tl, tr);

    int mn = max(a1.first, b1.first);
    int s = 0;
    if(a1.first == mn) s += a1.second;
    if(b1.first == mn) s += b1.second;
    return {mn, s};
}

int main(){
    ios_base::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;

    int n;
    cin >> n;
    vector <int> vec;
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        vec.push_back(a[i]);
        vec.push_back(b[i]);
        vec.push_back(c[i]);
        vec.push_back(d[i]);
    }
    sort(vec.begin(), vec.end());
    int cnt = 0;
    for(auto c : vec){
        if(!u[c]) u[c] = ++cnt;
    }
    for(int i=1; i<=n; i++){
        a[i] = u[a[i]];
        b[i] = u[b[i]];
        c[i] = u[c[i]];
        d[i] = u[d[i]];
        niz[i] = {c[i] , i};
        niz[i+n] = {d[i], i+n};
    }
    sort(niz+1, niz+1+2*n);
    for(int i=1; i<=2*n; i++){
        if(niz[i].second > n){
            //cout << b << " " << niz[i].second - n << endl;
            upd(1, 1, cnt+5, b[niz[i].second - n], niz[i].second - n);
        }
        else{
            int k = niz[i].second;
            //cout << a[k] << " " << k << endl;
            pair <int, int> rs = query(1, 1, cnt+5, 1, a[k]-1);
            dp[k] = rs.first + 1;
            brn[k] = rs.second;
            if(dp[k] == 1) brn[k] = 1;
        }
    }
    int res = 0;
    int mx = 0;
    for(int i=1; i<=n; i++){
        mx = max(mx, dp[i]);
    }
    for(int i=1; i<=n; i++){\
        //cout << dp[i] << " ";
        if(dp[i] == mx){
            res += brn[i];
            res %= MOD;
        }
    }
    cout << mx << " " << res;
    return 0;
}

• Subtask 1: 90 / 100