oj.uz

Submission #969891

# Submission time Handle Problem Language Result Execution time Memory
969891 2024-04-25T18:34:49 Z VinhLuu trapezoid (balkan11_trapezoid) C++17
0 / 100
 32 ms 65536 KB 
//#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<ll,ll> pii;
typedef tuple<int,int,int> tp;
const int N = 2e6 + 5;
const int mod = 30013;
//const ll oo = 5e18;

int n, a[N], b[N], c[N], d[N], mx = 1e6;
vector<int> open[N], close[N];

int st[N << 1], t[N << 1], f[N], g[N];

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};
}

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;
    for(int i = 1; i <= n; i ++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        open[a[i]].pb(i);
        close[b[i] + 1].pb(i);
    }

    for(int i = 1; i <= 1e6; i ++){
        for(auto j : close[i]){
            update(d[j], f[j], g[j]);
//            cerr << d[j] << " " << f[j] << " " << g[j] << " up\n";
        }
        for(auto j : open[i]){
            auto kq = get(1, c[j] - 1);
            f[j] = kq.fi + 1, g[j] = kq.se;
            if(f[j] == 1) g[j] = 1;
//            cerr << c[j] - 1 << " " << j << " " << f[j] << " " << g[j] << " y\n";
        }
    }
    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

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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 ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 65536 KB Execution killed with signal 9
2 Runtime error 14 ms 65536 KB Execution killed with signal 9
3 Runtime error 14 ms 65536 KB Execution killed with signal 9
4 Runtime error 14 ms 65536 KB Execution killed with signal 9
5 Runtime error 15 ms 65536 KB Execution killed with signal 9
6 Runtime error 14 ms 65536 KB Execution killed with signal 9
7 Runtime error 14 ms 65536 KB Execution killed with signal 9
8 Runtime error 14 ms 65536 KB Execution killed with signal 9
9 Runtime error 14 ms 65536 KB Execution killed with signal 9
10 Runtime error 16 ms 65536 KB Execution killed with signal 9
11 Runtime error 14 ms 65536 KB Execution killed with signal 9
12 Runtime error 14 ms 65536 KB Execution killed with signal 9
13 Runtime error 14 ms 65536 KB Execution killed with signal 9
14 Runtime error 14 ms 65536 KB Execution killed with signal 9
15 Runtime error 14 ms 65536 KB Execution killed with signal 9
16 Runtime error 15 ms 65536 KB Execution killed with signal 9
17 Runtime error 32 ms 65536 KB Execution killed with signal 9
18 Runtime error 15 ms 65536 KB Execution killed with signal 9
19 Runtime error 14 ms 65536 KB Execution killed with signal 9
20 Runtime error 14 ms 65536 KB Execution killed with signal 9