oj.uz

Submission #567371

# Submission time Handle Problem Language Result Execution time Memory
567371 2022-05-23T11:17:03 Z hgmhc trapezoid (balkan11_trapezoid) C++17
45 / 100
 500 ms 2604 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;
        cin >> t[i].fi.se >> t[i].se.se;
    }
    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 980 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 13 ms 1108 KB Output is correct
6 Correct 21 ms 1164 KB Output is correct
7 Correct 59 ms 1152 KB Output is correct
8 Correct 36 ms 1236 KB Output is correct
9 Correct 183 ms 1244 KB Output is correct
10 Execution timed out 1078 ms 1404 KB Time limit exceeded
11 Execution timed out 1082 ms 1412 KB Time limit exceeded
12 Execution timed out 1088 ms 1960 KB Time limit exceeded
13 Execution timed out 1094 ms 1980 KB Time limit exceeded
14 Execution timed out 1090 ms 2124 KB Time limit exceeded
15 Execution timed out 1067 ms 2160 KB Time limit exceeded
16 Execution timed out 1089 ms 2252 KB Time limit exceeded
17 Execution timed out 1096 ms 2400 KB Time limit exceeded
18 Execution timed out 1088 ms 2380 KB Time limit exceeded
19 Execution timed out 1091 ms 2508 KB Time limit exceeded
20 Execution timed out 1099 ms 2604 KB Time limit exceeded