oj.uz

Submission #1108550

# Submission time Handle Problem Language Result Execution time Memory
1108550 2024-11-04T11:55:05 Z Plot_Twist Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 336 KB 
#include<bits/stdc++.h>
#include<chrono>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std;
using namespace chrono;
#define ll long long
#define vl vector<long long>
#define endl '\n'
const int MOD = 1e9 + 7;
void inputv(vl &v) {for(int i = 0; i < (ll)v.size(); i++) cin>>v[i];}
void printv(vl v) {for(auto i : v) cout<<i<<" ";cout<<endl;}


#define int long long

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;


template <typename T>
class SegTree {
public:
    vector <T> tree;

    SegTree(int size) {
        tree.resize(size, 0);
    }

    T func(T a, T b) {
        return max(a, b); // Segment tree for the sum
        // return min(a, b); // Segment tree for the minimum
    }

    void update(int node, int start, int end, int pos, T val) {
        if(start == end) {
            tree[node] = val; // Assign value here.
        } else {
            int mid = (start + end)/2;
            if(pos <= mid) {
                update(node*2, start, mid, pos, val);
            } else {
                update(node*2 + 1, mid + 1, end, pos, val);
            }
            tree[node] = func(tree[node*2], tree[node*2 + 1]);
        }
    }

    T query(int node, int start, int end, int l, int r) {
        if(l > r) {
            return 0; // Return appropriate value, for example INF for minimum.
        }
        if(l == start && r == end) {
            return tree[node];
        }
        int mid = (start + end)/2;
        return func(query(node*2, start, mid, l, min(mid, r)), query(node*2 + 1, mid + 1, end, max(l, mid + 1), r));
    }
};

signed main() {

    ios::sync_with_stdio(false); cin.tie(NULL);
    int ts = 1;

    while(ts--) {
        int n,m;
        cin>>n>>m;
        vl arr(n);
        inputv(arr);
        map<int,int>mp;
        int ans = -1;
        int current = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] > current + m) {
                arr[i] = current+m;
                current = arr[i];
            }
            else {
                ans = i;
                break;
            }
        }
        if(ans==-1) {
            cout<<n<<endl;
            continue;
        }
        for(int i = ans; i< n; i++) mp[arr[i]];
        int temp = 0;
        for(auto &[a,b] : mp) b = temp++;

        SegTree<int>seg(temp<<2);
        seg.update(1,0,temp-1, mp[arr[ans]], 1);
        int ans_ = 1;
        for(int i = ans+1; i < n; i++) {
            int curr = mp[arr[i]];
            auto it = mp.lower_bound(arr[i] - m);
            int lq = (*it).second;
            int maxi = seg.query(1,0,temp-1,lq,temp-1);
            ans_ = max(ans_, maxi+1);
            seg.update(1,0,temp-1, curr, maxi+1);
        }
        cout<<n-ans_<<endl;
    }

    
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -