oj.uz

Submission #1060871

# Submission time Handle Problem Language Result Execution time Memory
1060871 2024-08-16T03:51:10 Z RiverFlow Osumnjičeni (COCI21_osumnjiceni) C++14
30 / 110
 332 ms 104060 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == 0) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

const int LG = 17;

int p[N], l[N], r[N], lg[N], sp[N][LG + 1];

int get(int l, int r) { int j = lg[r - l + 1];
    return min(sp[l][j], sp[r - (1 << j) + 1][j]);
}

int n;

namespace SUB1 {
    const int N = (int)5e3 + 3;

    int dp[N][N];

    void sol() {
        for(int i = 1; i <= n; ++i) {
            p[i] = n + 1;
            for(int j = i + 1; j <= n; ++j) {
                if ( l[i] > r[j] or r[i] < l[j] ) continue ;
                p[i] = j; break ;
            }
            sp[i][0] = p[i];
        }
        FOR(i, 2, n) lg[i] = lg[i / 2] + 1;
        for(int j = 1; (1 << j) <= n; ++j)
            for(int i = 1; i + (1 << j) - 1 <= n; ++i)
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);

        FOD(i, n, 1) {
            int num_seg = 0;
            int last_end = i;
            dp[i][i] = 1;
            for(int j = i + 1; j <= n; ++j) {
                if (get(last_end, j) > j) {
                    dp[i][j] = num_seg + 1;
                    continue ;
                }
                ++num_seg;
                last_end = j;
                dp[i][j] = num_seg + 1;
            }
        }
        int q; cin >> q;
        while (q--) {
            int l, r; cin >> l >> r;
            cout << dp[l][r] << nl;
        }
    }
};

struct segment_tree {
    int n;
    vector<int> t, lz;
    segment_tree (int _n) {
        n = _n;
        t.resize(4 * n + 7);
        lz.resize(4 * n + 7);
        FOR(i, 1, 4 * n) t[i] = n + 1;
    }
    void upd(int id, int l, int r, int u, int v, int val) {
        if (l > v or r < u) return ;
        if (l >= u and r <= v) {
            t[id] = val;
            lz[id] = val;
            return ;
        }
        if (lz[id]) {
            mini(t[id << 1], lz[id]);
            mini(t[id << 1 | 1], lz[id]);
            mini(lz[id << 1], lz[id]);
            mini(lz[id << 1 | 1], lz[id]);
            lz[id] = 0;
        }
        int m = (l + r) >> 1;
        upd(id << 1, l, m, u, v, val);
        upd(id << 1 | 1, m + 1, r, u, v, val);
        t[id] = min(t[id << 1], t[id << 1 | 1]);
    }
    void upd(int l, int r, int val) {
        upd(1, 1, n, l, r, val);
    }
    int get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return n + 1;
        if (l >= u and r <= v) return t[id];
        if (lz[id]) {
            mini(t[id << 1], lz[id]);
            mini(t[id << 1 | 1], lz[id]);
            mini(lz[id << 1], lz[id]);
            mini(lz[id << 1 | 1], lz[id]);
            lz[id] = 0;
        }
        int m = (l + r) >> 1;
        return min(get(id<<1,l,m,u,v), get(id<<1|1,m+1,r,u,v));
    }
    int get(int l, int r){
        return get(1,1,n,l,r);
    }

};

void main_code() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
    }
    if (n <= 5000) {
        SUB1::sol();
        return ;
    }

    vector<int> val;
    FOR(i, 1, n) {
        val.push_back(l[i]);
        val.push_back(r[i]);
    }
    unq(val);
    FOR(i, 1, n) {
        l[i] = lower_bound(all(val), l[i]) - val.begin() + 1;
        r[i] = lower_bound(all(val), r[i]) - val.begin() + 1;
    }
    segment_tree st(sz(val));
    FOD(i, n, 1) {
        p[i] = min(n + 1, st.get(l[i], r[i]));
        st.upd(l[i], r[i], i);
    }
    int q; cin >> q;

    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 1, mi = p[l];
        for(int i = l + 1; i <= n; ++i) {
            if (mi <= i) {
                ++ans;
                mi = p[i];
                continue ;
            }
            mi = min(mi, p[i]);
        }
        cout << ans << nl;
    }
}


/*     Let the river flows naturally     */

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 20044 KB Output is correct
2 Correct 293 ms 23596 KB Output is correct
3 Correct 284 ms 23752 KB Output is correct
4 Correct 284 ms 23752 KB Output is correct
5 Correct 303 ms 24516 KB Output is correct
6 Correct 35 ms 12240 KB Output is correct
7 Incorrect 38 ms 12236 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 102992 KB Output is correct
2 Correct 37 ms 96860 KB Output is correct
3 Correct 37 ms 98884 KB Output is correct
4 Correct 38 ms 100948 KB Output is correct
5 Correct 34 ms 96852 KB Output is correct
6 Correct 42 ms 102996 KB Output is correct
7 Correct 35 ms 98908 KB Output is correct
8 Correct 39 ms 102996 KB Output is correct
9 Correct 32 ms 98912 KB Output is correct
10 Correct 35 ms 98904 KB Output is correct
11 Correct 66 ms 102992 KB Output is correct
12 Correct 58 ms 98896 KB Output is correct
13 Correct 59 ms 98896 KB Output is correct
14 Correct 63 ms 102992 KB Output is correct
15 Correct 66 ms 102992 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 39 ms 101048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 102992 KB Output is correct
2 Correct 37 ms 96860 KB Output is correct
3 Correct 37 ms 98884 KB Output is correct
4 Correct 38 ms 100948 KB Output is correct
5 Correct 34 ms 96852 KB Output is correct
6 Correct 42 ms 102996 KB Output is correct
7 Correct 35 ms 98908 KB Output is correct
8 Correct 39 ms 102996 KB Output is correct
9 Correct 32 ms 98912 KB Output is correct
10 Correct 35 ms 98904 KB Output is correct
11 Correct 66 ms 102992 KB Output is correct
12 Correct 58 ms 98896 KB Output is correct
13 Correct 59 ms 98896 KB Output is correct
14 Correct 63 ms 102992 KB Output is correct
15 Correct 66 ms 102992 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 39 ms 101048 KB Output is correct
18 Correct 80 ms 101940 KB Output is correct
19 Correct 71 ms 99664 KB Output is correct
20 Correct 84 ms 104060 KB Output is correct
21 Correct 70 ms 99664 KB Output is correct
22 Correct 74 ms 97884 KB Output is correct
23 Correct 76 ms 101968 KB Output is correct
24 Correct 73 ms 101972 KB Output is correct
25 Correct 75 ms 97660 KB Output is correct
26 Correct 76 ms 103788 KB Output is correct
27 Correct 80 ms 101712 KB Output is correct
28 Correct 92 ms 99288 KB Output is correct
29 Correct 93 ms 99396 KB Output is correct
30 Correct 101 ms 99384 KB Output is correct
31 Correct 98 ms 97360 KB Output is correct
32 Correct 108 ms 103504 KB Output is correct
33 Correct 1 ms 6488 KB Output is correct
34 Correct 63 ms 99876 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 21108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 20044 KB Output is correct
2 Correct 293 ms 23596 KB Output is correct
3 Correct 284 ms 23752 KB Output is correct
4 Correct 284 ms 23752 KB Output is correct
5 Correct 303 ms 24516 KB Output is correct
6 Correct 35 ms 12240 KB Output is correct
7 Incorrect 38 ms 12236 KB Output isn't correct
8 Halted 0 ms 0 KB -