Submission #969900

#	Time	Username	Problem	Language	Result	Execution time	Memory
969900		VinhLuu	trapezoid (balkan11_trapezoid)	C++17	100 / 100	133 ms	24280 KiB

trapezoid

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int mod = 30013;
//const ll oo = 5e18;

int n, mx = 0;

int f[N], g[N];
vector<int> st, t;

void update(int i,int x,int cnt){
    i += mx - 1;
    if(st[i] < x) st[i] = x, t[i] = cnt; else if(st[i] == x) t[i] = (t[i] + cnt) % mod;
    while(i > 1){
        i /= 2;
        if(st[i] < x) st[i] = x, t[i] = cnt; else if(st[i] == x) t[i] = (t[i] + cnt) % mod;
    }
}

pii get(int l,int r){
    r++;
    int ret = 0, cnt = 0;
    for(l += mx - 1, r += mx - 1; l < r; l /= 2, r /= 2){
        if(l & 1){
            if(ret < st[l]) ret = st[l], cnt = t[l];
            else if(ret == st[l]) cnt = (cnt + t[l]) % mod;
            l++;
        }
        if(r & 1){
            --r;
            if(ret < st[r]) ret = st[r], cnt = t[r];
            else if(ret == st[r]) cnt = (cnt + t[r]) % mod;
        }
    }
    return {ret, cnt};
}
typedef tuple<int,int,int,int,int> op;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n;
    vector<int> rrh, ah;
    vector<op> ver;

    for(int i = 1; i <= n; i ++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        ver.push_back({i, a, b + 1, c, d});
        rrh.push_back(c);
        rrh.push_back(d);
        ah.push_back(a);
        ah.push_back(b + 1);
    }

    mx = rrh.size();
    sort(all(rrh));
    rrh.resize(unique(all(rrh)) - rrh.begin());
    st.push_back(0), t.push_back(0);
    for(auto j : rrh) st.push_back(0), st.push_back(0), t.push_back(0), t.push_back(0);

    int d = ah.size();
    vector<vector<pii>> open(d + 2), close(d + 2);

    sort(all(ah)); ah.resize(unique(all(ah)) - ah.begin());

    for(auto [id, a, b, c, d] : ver){
        a = lower_bound(all(ah), a) - ah.begin() + 1;
        b = lower_bound(all(ah), b) - ah.begin() + 1;
//        for(auto j : open[0]) cout << j << " \n";
        open[a].push_back({id, c});
        close[b].push_back({id, d});
    }

    for(int i = 1; i <= d; i ++){
        for(auto [id, j] : close[i]) update(lower_bound(all(rrh), j) - rrh.begin() + 1, f[id], g[id]);
        close[i].clear();
        for(auto [id, j] : open[i]){
            auto kq = get(1, lower_bound(all(rrh), j) - rrh.begin());
            f[id] = kq.fi + 1, g[id] = kq.se;
            if(f[id] == 1) g[id] = 1;
        }
        open[i].clear();
    }
    int ans = 0, cnt = 0;
    for(int i = 1; i <= n; i ++) if(ans < f[i]) ans = f[i], cnt = g[i]; else if(ans == f[i]) cnt = (cnt + g[i]) % mod;
    cout << ans << " " << cnt;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:78:14: warning: unused variable 'j' [-Wunused-variable]
   78 |     for(auto j : rrh) st.push_back(0), st.push_back(0), t.push_back(0), t.push_back(0);
      |              ^
trapezoid.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100