Submission #1054598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054598		Itamar	Financial Report (JOI21_financial)	C++14	100 / 100	671 ms	82220 KiB

Main

using namespace std;
#include <iostream>
#include<map>
#include <vector>
#define vi vector<int>
#define pi pair<int,int>
#define ll long long
#include<set>
#define ckmin(a,b) a = min(a,b)
#define ckmax(a,b) a = max(a,b)
const int siz = 3e5+2;
int n,d;
int A[siz];
int r[siz];

map<int,vi> m;
set<int> s;
struct dsu{
    int pad[siz];
    dsu(){
        for(int i =0 ; i < siz; i++)pad[i]=i;
    }
    int root(int a){
        if(pad[a]==a)return a;
        return pad[a] = root(pad[a]);
    }
    void connect(int a, int b){
        a = root(a), b = root(b);
        if(a==b)return;
        pad[min(a,b)]=max(a,b);
    }
};
vi getlr(int i){
    auto it1 = s.lower_bound(i);
    int af = (it1 == s.end() ? -1 : *it1);
    if(it1 == s.begin())return {-1,af};
    it1--;
    return {*it1,af};
}
dsu ds;
void findr(){
    for(auto[a,v] : m){
        for(int i : v){
            auto adj = getlr(i);
            for(int prev : adj){
                if(prev!=-1 && abs(prev-i)<=d){
                ds.connect(i,prev);
                }
            }
            s.insert(i);
        }
        for(int i : v)r[i] = ds.root(i);
    }
    
}
struct node{
  int l,r,mid,maxi;
  node* sl,*sr;
  node(int li, int ri){
    l = li, r = ri, mid = (l+r)/2, maxi = 0;
    if(l<r){
        sl = new node(l,mid);
        sr = new node(mid+1,r);
    }
  }  
  void update(int i, int val){
    if(l == r){
        maxi = val;
    }else{
        if(i <= mid)sl->update(i,val);
        else sr->update(i,val);
        maxi = max(sl->maxi,sr->maxi);
    }
  }
  int query(int a, int b){
    if(a > r || b < l)return 0;
    if(a <= l && b>=r)return maxi;
    return max(sl->query(a,b),sr->query(a,b));
  }
};
int ans = 0;
node* seg;
void dp(){
    for(auto it = m.rbegin(); it != m.rend(); it++){
        auto [a,v] = *it;
        int si  = v.size();
        vi up(si);
        for(int i = 0; i < si; i++){
            up[i] = seg->query(v[i]+1,r[v[i]])+1;
        }
        for(int i = 0; i < si; i++){
            ans = max(ans,up[i]);
            seg->update(v[i],up[i]);
        }
    }
}
int main(){
    cin >> n >> d;
    for(int i = 0; i < n; i++)cin >> A[i];

    for(int i = 0; i < n; i++)m[A[i]].push_back(i);
    findr();
    for(int i = 0; i < n;i++)r[i] = min(r[i]+d,n-1);

    seg = new node(0,n-1);
    dp();
    
    cout << ans;
        

}

Compilation message (stderr)

Main.cpp: In function 'void findr()':
Main.cpp:42:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto[a,v] : m){
      |             ^
Main.cpp: In function 'void dp()':
Main.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto [a,v] = *it;
      |              ^

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