Submission #1126125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126125		qwewq	Financial Report (JOI21_financial)	C++20	0 / 100	4097 ms	58256 KiB

Main

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 3e5 + 2;
int par[N + 2];
int cc[N + 2];
vector < int > vt;
set < int > s;
int find_par(int u){
    if(par[u] < 0)return u;
    return par[u] = find_par(par[u]);
}
void union_set(int u , int v){
    u = find_par(u);
    v = find_par(v);
    if(u != v){
        if(par[u] > par[v])swap(u , v);
        par[u]  += par[v];
        par[v] = u;
        cc[u] = max(cc[u] , cc[v]);
    }
}
int a[N + 2];
multiset< int > sx[N + 2]; 
bool cmp(int g , int h){
    if(a[g]  != a[h])return a[g] < a[h];
    return g > h;
}
int nxt[N + 2];
int st[4  * N + 2];
int n , d;
vector < pair < int , int > > query[N + 2];
void update(int id , int l , int r  , int p , int val , bool cc){
    if(l > p || r  < p)return;
    if(l == r){
        if(cc){
            sx[l].insert(val);
        }
        else{
            sx[l].erase(sx[l].find(val));
        }
        if(sx[l].size())st[id] =  *sx[l].rbegin();
        else st[id] =  0;
        return;
    }
    int mid = (l  + r) / 2;
    update(id * 2 , l , mid , p , val , cc);
    update(id * 2 + 1 , mid  + 1 , r , p , val ,cc);
    st[id] = max(st[id  * 2] , st[id  * 2 + 1]);
}
int get(int id , int l  , int r , int u , int v){
    if(l > v ||  r < u)return  0;
    if(u <= l && r  <= v){
        return st[id];
    }
    int mid = (l + r) / 2;
    return max(get(id * 2 , l , mid , u , v) , get(id * 2 + 1 , mid + 1 , r , u , v)); 
}
void pre(){
    sort(vt.begin() , vt.end());
    vt.erase(unique(vt.begin() , vt.end()) ,  vt.end());
    vector <int > res;
    for(int  i = 1; i <= n ; i ++){
        a[i] = upper_bound(vt.begin()  ,vt.end() , a[i]) - vt.begin();
        res.push_back(i);
        cc[i] = i + d;
    }
    memset(par , -1 , sizeof(par));
    sort(res.begin()  , res.end() , cmp);
    for(auto v: res){
        if(s.size()){
            auto it = s.lower_bound(v);
            if(it != s.begin()){
                it--;
               if(v - *it <= d) union_set(v , *it);
            }
            it = s.upper_bound(v);
            if(it != s.end()){
                if(*it -  v <= d) union_set(v , *it);
            }
        }
        nxt[v] = cc[find_par(v)];
        s.insert(v);
    }
}
void solve() {
    cin >> n >> d;
    for(int  i =1; i <= n ; i ++){
        cin >> a[i];
        vt.push_back(a[i]);
    }
    pre();
    int ans = 0;
    for(int i = 1; i <= n ;i ++){
        int val = get(1 , 1 , n , 1 , a[i] - 1) + 1;
        ans = max(ans , val);
        update(1 , 1 , n , a[i]  , val , 1);
        query[nxt[i]].push_back({i , val});
        for(auto[u , val] : query[i]){
            update(1 , 1 , n , u , val , 0);
        }
    }
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    #define _ "GRAPHZIP."
    if (fopen(_ "inp", "r")) {
        freopen(_ "inp", "r", stdin);
        freopen(_ "out", "w", stdout);
    }
    
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(_ "inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(_ "out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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