Submission #884239

#	Time	Username	Problem	Language	Result	Execution time	Memory
884239		HorizonWest	Financial Report (JOI21_financial)	C++17	100 / 100	619 ms	54100 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

struct SegmentTree
{
    struct node
    {
        int val;

        node(int v = 0)
        {
            val = v;
        }
    };

    vector <node> tree; int l;

    node merge(node a, node b)
    {
        return node(max(a.val, b.val));
    }

    void update(int k, int v)
    {
        k += (l - 1); tree[k] = node(v);
        for(k /= 2; k > 0; k /= 2)
            tree[k] = merge(tree[2*k], tree[2*k+1]);
    }

    node query(int k, int x, int y, int s, int e)
    {
        if(s > y || e < x)
            return node();
        if(s >= x && e <= y)
            return tree[k];

        int middle = (s + e) / 2;

        return merge(query(2*k, x, y, s, middle),
            query(2*k+1, x, y, middle + 1, e));
    }

    int query(int x, int y)
    {
        node ans = query(1, x, y, 1, l);
        return ans.val;
    }

    SegmentTree(int n)
    {
        for(l = 1; l < n; (l <<= 1));
        tree.assign(2 * l, node());
    }
};

struct SegmentTreePos
{
    struct node
    {
        int val, pos;

        node(int v = 0, int p = 0)
        {
            val = v; pos = p; 
        }
    };

    vector <node> tree; int l;

    node merge(node a, node b)
    {
        if(a.val == 0)
            return node(b.val, b.pos);     
        else 
            return node(a.val, a.pos);
    }

    void update(int k, int v)
    {
        k += (l - 1); tree[k] = node(v, k - (l - 1)); //cout << "UPDATE: " << k - (l - 1) << " " << v << endl; 
        for(k /= 2; k > 0; k /= 2)
            tree[k] = merge(tree[2*k], tree[2*k+1]);
    }

    node query(int k, int x, int y, int s, int e)
    {
        if(s > y || e < x)
            return node();
        if(s >= x && e <= y)
            return tree[k];

        int middle = (s + e) / 2;

        return merge(query(2*k, x, y, s, middle),
            query(2*k+1, x, y, middle + 1, e));
    }

    pair <int, int> query(int x, int y)
    {
        node ans = query(1, x, y, 1, l);
        return { ans.val, ans.pos };
    }

    SegmentTreePos(int n)
    {
        for(l = 1; l < n; (l <<= 1));
        tree.assign(2 * l, node());
    }
};

void solve()
{
    int n, d; cin >> n >> d; 
    SegmentTree St1(n+2);
    SegmentTreePos St2(n+2);
    vector <pair<int, int>> f(n);
    vector <int> v(n); 
    for(int i = 0; i < n; i++)
    {
        cin >> v[i]; 
        f[i].fs = v[i]; f[i].sd = i; 
    } 
    sort(all(f)); 

    map <int, int> mp; 

    for(int i = 0; i < n; i++)
        mp[f[i].fs] = i + 2; 

    for(int i = 1; i <= n; i++)
    {
        int x = mp[v[i-1]]; pair <int, int> y = St2.query(1, n+2); //cerr << "I: " << i << " X: " << x << "    - " << y.fs << " " << y.sd << " " << i - d << endl; 

        while ((y.fs < i - d) && y.fs != 0) // HERE
        {
            St1.update(y.sd, 0); //cerr << "PASA: " << y.fs << " " << y.sd << endl; 
            St2.update(y.sd, 0); 
            y = St2.query(1, n+2); 
        }
        
        St1.update(x, max(St1.query(x, x), St1.query(1, x - 1) + 1));
        St2.update(x, i); 
    }

    cout << St1.query(1, n+2) << endl; 
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35