Submission #469125

#	Time	Username	Problem	Language	Result	Execution time	Memory
469125		Vladth11	Financial Report (JOI21_financial)	C++14	5 / 100	747 ms	428996 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 600001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;

int dp[NMAX];
int v[NMAX];
map <int, int> mp;
int n;

class AINT{
public:
    deque <pii> a[NMAX];
    int aint[NMAX * 4];
    void update(int node, int st, int dr, int poz, pii x){
        if(st == dr){
            while(a[st].size() && a[st].back().first <= x.first)
                a[st].pop_back();
            a[st].push_back(x);
            aint[node] = a[st].front().first;
            return;
        }
        int mid = (st + dr) / 2;
        if(poz <= mid){
            update(node * 2, st, mid, poz, x);
        }else{
            update(node * 2 + 1, mid + 1, dr, poz, x);
        }
        aint[node] = max(aint[node * 2],  aint[node * 2 + 1]);
    }
    void sterge(int node, int st, int dr, int poz, int x){
        if(st == dr){
            while(a[st].size() && a[st].front().second < x)
                a[st].pop_front();
            if(a[st].size())
            aint[node] = a[st].front().first;
            else aint[node] = 0;
            return;
        }
        int mid = (st + dr) / 2;
        if(poz <= mid){
            sterge(node * 2, st, mid, poz, x);
        }else{
            sterge(node * 2 + 1, mid + 1, dr, poz, x);
        }
        aint[node] = max(aint[node * 2],  aint[node * 2 + 1]);
    }
    int query(int node, int st, int dr, int a, int b){
        if(a <= st && dr <= b){
            return aint[node];
        }
        int mid = (st + dr) / 2;
        int maxim = 0;
        if(a <= mid){
            maxim = max(maxim, query(node * 2, st, mid, a, b));
        }
        if(b > mid){
            maxim = max(maxim, query(node * 2 + 1, mid + 1, dr, a, b));
        }
        return maxim;
    }
    void insert(int poz, pii x){
        update(1, 1, NMAX - 1, poz, x);
    }
    void erase(int poz, int upd){
        sterge(1, 1, NMAX - 1, poz, upd);
    }
}aint;

int nrm[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, d;
    cin >> n >> d;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        nrm[i] = v[i];
    }
    sort(v + 1, v + n + 1);
    int cnt = 0;
    for(i = 1; i <= n; i++){
        if(i == 1 || v[i] != v[i - 1])
            cnt++;
        mp[v[i]] = cnt;
    }
    for(i = 1; i <= n; i++){
        v[i] = nrm[i];
        v[i] = mp[v[i]];
    }
    int maxim = 0;
    /// de incercat normalizarea mai rapid
    for(i = 1; i <= n; i++){
        if(i > d + 1){
            aint.erase(v[i - d - 1], i - d);
        }
        if(v[i] > 1)
        dp[i] = aint.query(1, 1, NMAX - 1, 1, v[i] - 1) + 1;
        else dp[i] = 1;
        maxim = max(maxim, dp[i]);
        aint.insert(v[i], {dp[i], i});
    }
    cout << maxim;
    return 0;
}

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