Submission #713519

#	Time	Username	Problem	Language	Result	Execution time	Memory
713519		Ronin13	Financial Report (JOI21_financial)	C++14	100 / 100	908 ms	41832 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 500001;

vector <int> t(4 * nmax);
vector <bool> lazy(4 * nmax, 0);

void push(int v){
    if(lazy[v]){
        t[2 * v] = t[2 * v + 1] = 0;
        lazy[v * 2] = lazy[v * 2 + 1] = true;
        lazy[v] = false;
    }
}

void update(int v, int l, int r, int st, int fin){
    if(l > fin || r < st){
        return;
    }
    if(l >= st && r <= fin){
        t[v] = 0;
        lazy[v] = true;
        return;
    }
    int m = (l + r) / 2;
    push(v);
    update(2 * v, l, m, st, fin);
    update(2 * v + 1, m+ 1, r, st, fin);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

void upd_p(int v, int l, int r, int pos, int val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v] = max(t[v], val);
        return;
    }
    int m = (l + r) / 2;
    push(v);
    upd_p(2 * v, l, m, pos, val);
    upd_p(2 * v + 1, m + 1, r, pos, val);
    t[v]= max(t[2 * v], t[2 * v + 1]);
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 0;
    if(l >= st && r <= fin)
        return t[v];
    push(v);
    int m = (l + r) / 2;
    return max(get(2 * v, l, m, st, fin),
               get(2 * v + 1, m + 1, r, st, fin));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, d; cin >> n >> d;
    int a[n + 1];
    vector <int> comp;
    map <int, int> mp;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        comp.pb(a[i]);
    }
    sort(comp.begin(), comp.end());
    for(int i= 0; i < comp.size(); i++)
        mp[comp[i]] = i + 1;
    for(int i= 1; i <= n; i++)
        a[i] = mp[a[i]];
    multiset <int> st;
    for(int i = 1; i <= n; i++){
        int x = get(1, 1, n, 1, a[i] - 1);
        upd_p(1, 1, n, a[i], x + 1);
        st.insert(a[i]);
        if(st.size() < d) continue;
        if(st.size() > d)
            st.erase(st.find(a[i - d]));
        update(1, 1, n, 1, *st.begin() - 1);
    }
    cout << t[1];
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i= 0; i < comp.size(); i++)
      |                   ~~^~~~~~~~~~~~~
Main.cpp:85:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         if(st.size() < d) continue;
      |            ~~~~~~~~~~^~~
Main.cpp:86:22: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if(st.size() > d)
      |            ~~~~~~~~~~^~~

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