Submission #469227

#	Time	Username	Problem	Language	Result	Execution time	Memory
469227		Vladth11	Financial Report (JOI21_financial)	C++14	100 / 100	783 ms	242800 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 = 300001;
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 bloc[NMAX];
int aib[NMAX];
 
void update(int node, int val){
    for(; node > 0; node -= node&(-node)){
        aib[node] = min(aib[node], val);
    }
}
 
int query(int node){
    int minim = 2e9;
    for(; node < NMAX; node += node&(-node)){
        minim = min(minim, aib[node]);
    }
    return minim;
}
 
vector <int> del[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];
    }
    for(i = NMAX - 1; i > 0; i--)
        aib[i] = 2e9;
    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;
    deque <int> minim; /// si aici putem face o schema
    for(i = n; i > n - d + 1; i--){
        while(minim.size() && minim.back() > v[i])
            minim.pop_back();
        minim.push_back(v[i]);
    }
    for(i = n - d + 1; i >= 1; i--){
        if(i <= n - d){
            if(minim.size() && minim.front() == v[i + d])
                minim.pop_front();
        }
         while(minim.size() && minim.back() > v[i])
            minim.pop_back();
        minim.push_back(v[i]);
        bloc[i] = minim.front();
    }
    for(i = n - d + 1; i >= 1; i--){
        int unde = query(v[i] + 1);
        if(unde <= n) /// putem avea si n + 1
            del[unde].push_back(i);
        update(bloc[i], i + d);
    }
    /// de incercat normalizarea mai rapid
    for(i = 1; i <= n; i++){
        for(auto x : del[i]){
            aint.erase(v[x], x + 1);
        }
        if(v[i] > 1)
        dp[i] = aint.query(1, 1, NMAX - 1, 1, v[i] - 1) + 1;
        else dp[i] = 1;
        aint.insert(v[i], {dp[i], i});
    }
    cout << aint.query(1, 1, NMAX - 1, 1, NMAX - 1);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:130:9: warning: unused variable 'maxim' [-Wunused-variable]
  130 |     int maxim = 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