oj.uz

Submission #856489

# Submission time Handle Problem Language Result Execution time Memory
856489 2023-10-03T16:44:26 Z ArminAzimi trapezoid (balkan11_trapezoid) C++14
100 / 100
 144 ms 17088 KB 
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair <int, int>, null_type,less<pair <int, int>>, rb_tree_tag,tree_order_statistics_node_update> 

const int MAXN = 2e5 + 10, MAXM = 1e2 + 10, MOD = 30013, MOD1 = 1e9 + 9, SQ = 350;
const long long INF = 1e9 + 11;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int id_a[MAXN], id_b[MAXN];
int seg[4 * MAXN], fen[MAXN];
int dp[MAXN];
vector <int> vec[MAXN];
int cnt[MAXN];

void upd(int l, int r, int id, int ind, int val) {
    if (l == r) {
        seg[id] = val;
        return;
    }

    int mid = (l + r) / 2;
    if (ind <= mid)
        upd(l, mid, 2 * id, ind, val);
    else
        upd(mid + 1, r, 2 * id + 1, ind, val);

    seg[id] = max(seg[2 * id], seg[2 * id + 1]);
}

int get(int l, int r, int id, int l1, int r1) {
    if (r < l1 || r1 < l)
        return 0;
    if (l1 <= l && r <= r1)
        return seg[id];
    
    int mid = (l + r) / 2;
    return max(get(l, mid, 2 * id, l1, r1), get(mid + 1, r, 2 * id + 1, l1, r1));
}

void upd(int x, int val) {
    x++;
    for (; x < MAXN; x += x & (-x))
        fen[x] = (fen[x] + val) % MOD;
}

int get(int x) {
    x++;
    int res = 0;
    for (; x; x -= x & (-x))
        res = (res + fen[x]) % MOD;
    return res;
}


void solve() {
    int n;
    cin >> n;

    vector <int> kol1, kol2;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        kol1.push_back(a[i]);
        kol1.push_back(b[i]);
        kol2.push_back(c[i]);
        kol2.push_back(d[i]);
    }

    sort(kol1.begin(), kol1.end());
    kol1.resize(unique(kol1.begin(), kol1.end()) - kol1.begin());

    sort(kol2.begin(), kol2.end());
    kol2.resize(unique(kol2.begin(), kol2.end()) - kol2.begin());

    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(kol1.begin(), kol1.end(), a[i]) - kol1.begin();
        b[i] = lower_bound(kol1.begin(), kol1.end(), b[i]) - kol1.begin();
        c[i] = lower_bound(kol2.begin(), kol2.end(), c[i]) - kol2.begin();
        d[i] = lower_bound(kol2.begin(), kol2.end(), d[i]) - kol2.begin();

        id_a[a[i]] = i;
        id_b[b[i]] = i;
    }

    for (int i = 0; i < 2 * n; i++) {
        if (id_a[i]) {
            int ind = id_a[i];
            int l1 = c[ind];

            dp[i] = get(0, 2 * n, 1, 0, l1) + 1;    
        }
        else {
            int ind = id_b[i];
            int index = d[ind];

            upd(0, 2 * n, 1, index, dp[a[ind]]);
        }
    }
    
    int ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (id_a[i]) {
            ans = max(ans, dp[i]);
            vec[dp[i]].push_back(id_a[i]);
        }
    }

    for (int i = 0; i < vec[1].size(); i++)
        cnt[vec[1][i]] = 1;
    
    for (int i = 1; i < ans; i++) {
        vector <pair <int, bool>> t;
        for (int ind: vec[i])
            t.push_back({b[ind], 0});
        for (int ind: vec[i + 1])
            t.push_back({a[ind], 1});

        sort(t.begin(), t.end());

        for (pair <int, int> t1: t) {
            int x = t1.first;
            bool f = t1.second;

            if (f == 0) {
                int ind = id_b[x];
                upd(d[ind], cnt[ind]);
            }
            else {
                int ind = id_a[x];
                cnt[ind] = get(c[ind]);
            }
        }

        for (pair <int, int> t1: t) {
            int x = t1.first;
            bool f = t1.second;

            if (f == 0) {
                int ind = id_b[x];
                upd(d[ind], -cnt[ind]);
            }
        }
    }

    int ans1 = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (id_a[i]) {
            if (dp[i] == ans) {
                ans1 += cnt[id_a[i]];
                ans1 %= MOD;
            }
        }
    }

    cout << ans << " " << ans1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    // cin >> q;
    
    while (q--) {
        solve();
    }
}

Compilation message

trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < vec[1].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12632 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 4 ms 12840 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 7 ms 12956 KB Output is correct
9 Correct 13 ms 13404 KB Output is correct
10 Correct 30 ms 13964 KB Output is correct
11 Correct 30 ms 14124 KB Output is correct
12 Correct 73 ms 15304 KB Output is correct
13 Correct 74 ms 15556 KB Output is correct
14 Correct 86 ms 16320 KB Output is correct
15 Correct 103 ms 16484 KB Output is correct
16 Correct 105 ms 16544 KB Output is correct
17 Correct 117 ms 16900 KB Output is correct
18 Correct 103 ms 16700 KB Output is correct
19 Correct 115 ms 16900 KB Output is correct
20 Correct 144 ms 17088 KB Output is correct