Submission #1119594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119594		Thunnus	trapezoid (balkan11_trapezoid)	C++17	43 / 100	136 ms	31000 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MOD = 30013;

struct MAXBIT{
    vi bit;
    MAXBIT(int n) : bit(n + 1) {}

    inline void add(int idx, int val){
        for(++idx; idx < sz(bit); idx += idx & -idx){
            bit[idx] = max(val, bit[idx]);
        }
        return;
    }

    inline int query(int idx){
        int ret = 0;
        for(++idx; idx; idx -= idx & -idx){
            ret = max(ret, bit[idx]);
        }
        return ret;
    }
};

struct SUMBIT{
    vi bit;
    SUMBIT(int n) : bit(n + 1) {}

    inline void add(int idx, int val){
        for(++idx; idx < sz(bit); idx += idx & -idx){
            bit[idx] = (bit[idx] + val) % MOD;
        }
        return;
    }

    inline int query(int idx){
        int ret = 0;
        for(++idx; idx; idx -= idx & -idx){
            ret = (ret + bit[idx]) % MOD;
        }
        return ret;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, a, b, c, d;
    cin >> n;
    vi cord;
    vector<array<int, 4>> trap(n);
    for(int i = 0; i < n; i++){
        cin >> a >> b >> c >> d;
        cord.emplace_back(a), cord.emplace_back(b), cord.emplace_back(c), cord.emplace_back(d);
        trap[i] = {a, b, c, d};
    }
    sort(cord.begin(), cord.end());
    cord.erase(unique(cord.begin(), cord.end()), cord.end());

    auto compress = [&](int idx) -> int {
        return lower_bound(cord.begin(), cord.end(), idx) - cord.begin();
    };

    vector<array<int, 4>> ev;
    for(int i = 0; i < n; i++){
        trap[i] = {compress(trap[i][0]), compress(trap[i][1]), compress(trap[i][2]), compress(trap[i][3])};
        ev.push_back({trap[i][0], trap[i][2], i, 1});
        ev.push_back({trap[i][1], trap[i][3], i, 2});
    }
    sort(ev.begin(), ev.end());
    
    MAXBIT maxbit(4 * n + 4);
    vi mx(n), dp(n);
    vector<vector<array<int, 3>>> mx2ev(n + 1);
    for(array<int, 4> &e : ev){
        if(e[3] == 1){
            mx[e[2]] = maxbit.query(e[1]);
            mx2ev[mx[e[2]]].push_back({e[1], e[2], 0});
            if(mx[e[2]] > 0){
                mx2ev[mx[e[2]] - 1].push_back({e[1], e[2], 1});
            }
            else{
				dp[e[2]] = 1;
			}
        }
        else{
            maxbit.add(e[1], mx[e[2]] + 1);
        }
    }
	
	int max_len = maxbit.query(4 * n - 1);
    SUMBIT sumbit(4 * n + 4);
    for(int i = 0; i < max_len; i++){
        for(array<int, 3> &e : mx2ev[i]){
            if(!e[2]){
                sumbit.add(e[0], dp[e[1]]);
            }
            else{
                dp[e[1]] = sumbit.query(e[0]);
            }
        }
        for(array<int, 3> &e : mx2ev[i]){
            if(!e[2]){
                sumbit.add(e[0], -dp[e[1]]);
            }
        }
    }
    int ways = 0;
    for(int i = 0; i < n; i++){
        if(mx[i] + 1 == max_len){
            ways = (ways + dp[i]) % MOD;
        }
    }
    cout << max_len << " " << ways << "\n";
    return 0;
}

• Subtask 1: 43 / 100