oj.uz

Submission #567370

# Submission time Handle Problem Language Result Execution time Memory
567370 2022-05-23T11:16:44 Z hgmhc trapezoid (balkan11_trapezoid) C++17
45 / 100
 500 ms 4368 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define fi first
#define se second
#define Mup(x,y) x = max(x,y)

const int N = 1e5+3;
int n;
pair<ii,ii> t[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    vector<int> xs, ys;
    rep(i,1,n) {
        cin >> t[i].fi.fi >> t[i].se.fi;
        xs.push_back(t[i].fi.fi), xs.push_back(t[i].se.fi);
        cin >> t[i].fi.se >> t[i].se.se;
        ys.push_back(t[i].fi.se), ys.push_back(t[i].se.se);
    }
    sort(all(xs)), xs.erase(unique(all(xs)),end(xs));
    sort(all(ys)), ys.erase(unique(all(ys)),end(ys));
    rep(i,1,n) {
        t[i].fi.fi = lower_bound(all(xs),t[i].fi.fi)-begin(xs);
        t[i].fi.se = lower_bound(all(ys),t[i].fi.se)-begin(ys);
        t[i].se.fi = lower_bound(all(xs),t[i].se.fi)-begin(xs);
        t[i].se.se = lower_bound(all(ys),t[i].se.se)-begin(ys);
    }
    sort(t+1,t+n+1);
    int lis[N] {0,}, cnt[N] {0,};
    int ans1 = 0, ans2 = 0;
    rep(i,1,n) {
        lis[i] = 1, cnt[i] = 1;
        rep(j,1,n-1) {
            if (t[j].se.fi < t[i].fi.fi and t[j].se.se < t[i].fi.se) {
                if (lis[i] < lis[j]+1) {
                    lis[i] = lis[j]+1;
                    cnt[i] = cnt[j];
                } else if (lis[i] == lis[j]+1)
                    cnt[i] = (cnt[i]+cnt[j])%30013;
            }
        }
        Mup(ans1, lis[i]);
    }
    rep(i,1,n) if (ans1 == lis[i])
        ans2 = (ans2+cnt[i])%30013;
    cout << ans1 << ' ' << ans2;
}

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 5 ms 1108 KB Output is correct
5 Correct 13 ms 1196 KB Output is correct
6 Correct 23 ms 1236 KB Output is correct
7 Correct 63 ms 1236 KB Output is correct
8 Correct 40 ms 1364 KB Output is correct
9 Correct 179 ms 1556 KB Output is correct
10 Execution timed out 1084 ms 1872 KB Time limit exceeded
11 Execution timed out 1094 ms 2096 KB Time limit exceeded
12 Execution timed out 1084 ms 2888 KB Time limit exceeded
13 Execution timed out 1089 ms 3092 KB Time limit exceeded
14 Execution timed out 1091 ms 3880 KB Time limit exceeded
15 Execution timed out 1075 ms 3864 KB Time limit exceeded
16 Execution timed out 1090 ms 3908 KB Time limit exceeded
17 Execution timed out 1090 ms 3960 KB Time limit exceeded
18 Execution timed out 1089 ms 4136 KB Time limit exceeded
19 Execution timed out 1087 ms 4180 KB Time limit exceeded
20 Execution timed out 1090 ms 4368 KB Time limit exceeded