Submission #525186

#	Time	Username	Problem	Language	Result	Execution time	Memory
525186		Maillew	Global Warming (CEOI18_glo)	C++14	100 / 100	291 ms	18116 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <fstream>
using namespace std;
using namespace __gnu_pbds;
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> os;

typedef long long ll;

typedef long double ld;
typedef pair<int,int> pii;
bool DEBUG = 1;
#define log2(x) ((x==0)? 0:63 - __builtin_clzll(x))
#define pb push_back
#define deb(x) if(DEBUG) cout<<#x<<" " <<x<<"\n";
#define ms(x, y) memset(x, y, sizeof x)
#define popcount __builtin_popcount
#define all(v) v.begin(), v.end()

const int inf=0x3f3f3f3f; const ll LLINF=0x3f3f3f3f3f3f3f3f;
inline ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
inline ll lcm(ll a, ll b) { return (a / gcd(a, b))*b;}
template<typename... T> void deb2(T&&... args){ if(DEBUG) ((cout<<args<<" "), ...); if(DEBUG) cout<<"\n";}

const ll mod = 1e9+7;
struct tri{
    ll x,y,z;
    bool operator<(const tri &one)const{
        if(x==one.x) return y<one.y;
        return x<one.x;
    }//pqs are backwards
    //need to fill in comparator for remaining, if u are putting it into a map/set or sumn
};
ll fpow(ll a, ll b){
    if (b == 0) return 1;
    ll res = fpow(a, b / 2)%mod;
    if (b % 2) return ((res * res)%mod * a)%mod;
    else return (res * res)%mod;
}
//if ur brute force sol gets WA, when it should TLE, ur brute force is wrong; make it even more brute force
    //assert ideas with ur slow, to find out why ur fast WA
//make sure to fully actuate your ideas before coding it up; spend more time on samples and examples

//MAKE SURE UR ARRAY BOUNDS ARE CORRECT: IT CAN ALSO LEAD TO WA
//try not to spam sub; be more thoughtful when submitting -> prevents tilt, and more likely to not WA
//cant compile == MLE
//be wary of sunk cost fallacy, sometimes its better to let go of an idea if its not working
//practice debugging wo fast slow; not all problems can use it, and it takes a while to set up
/*
    *int overflow, array bounds
    *special cases n=1, n=0,
    *reread when stuck -> couldve missed small detail
    *write stuff down
    *DONT GET STUCK ON ONE APPROACH
*/
//on contests, take ur time to prevent misreading
    //if WA, think carefully abt edge cases etc, and reread
//idea sheet
//make sure u are on the correct file when submitting; fast slow
struct SegTree{
    vector<ll> seg;
    int _n;
    void init(int n){
        _n =n;
        seg.resize(4*(n+10));
        for(int i =0; i<seg.size(); i++) seg[i] = 0;
    }
    void updd(int l, int r, int pos, ll v, int ind){
        if(l == r && pos == r){
            seg[ind] = max(seg[ind],v);
            return;
        }
        int mid = (l+r)/2;
        if(pos<=mid) updd(l,mid,pos,v,2*ind);
        else updd(mid+1,r,pos,v,2*ind+1);
        seg[ind] = max(seg[2*ind],seg[2*ind+1]);
    }
    ll queryy(int l, int r, int li, int ri, int ind){
        if(ri<l || r<li) return 0;
        if(li<=l && r<=ri){
            return seg[ind];
        }
        int mid = (l+r)/2;
        return max(queryy(l,mid,li,ri,2*ind),queryy(mid+1,r,li,ri,2*ind+1));
    }
    void upd(int pos,ll v){
        updd(1,_n,pos,v,1);
    }
    ll query(int l, int r){
        return queryy(1,_n,l,r,1);
    }
};
const int maxn = 2e5+10;
int arr[maxn];
vector<int>d;
int n,x;
int LDS[maxn];//length of LDS from n..i -> used to join with prefix LIS, ENDING with element i; LIS should be the same
int LIS[maxn]; //length of LIS from 1..i
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>x;
    for(int i =1; i<=n; i++){
        cin>>arr[i];
        d.pb(arr[i]);
    }
    sort(all(d));
    d.resize(unique(all(d))-d.begin());

    for(int i =1; i<=n; i++){
        arr[i] = lower_bound(all(d),arr[i])-d.begin()+1;
    }
    //strict LIS
    //LIS ENDING at each value -> use seg
    SegTree lis; lis.init(n);
    for(int i =1; i<=n; i++){
        LIS[i] = lis.query(1,arr[i]-1)+1;
        lis.upd(arr[i],LIS[i]);
    }
    lis.init(n);
    for(int i =n; i>=1; i--){
        LDS[i] = lis.query(arr[i]+1,n)+1;
        lis.upd(arr[i],LDS[i]);
    }
//    for(int i =1; i<=n; i++){
//        cout<<LIS[i]<<" ";
//    }
//    cout<<"\n";
//    for(int i =1; i<=n; i++){
//        cout<<LDS[i]<<" ";
//    }
//    cout<<"\n";
    //point update, range query
    SegTree seg; seg.init(n);
    ll ans =0;

    for(int i =1; i<=n; i++){
        //decrement 1...i-1;
        int val = d[arr[i]-1]+x-1;
        int it = upper_bound(all(d),val)-d.begin();
        ans = max(ans, seg.query(1,it)+LDS[i]);
//        deb2(val,it,seg.query(1,it),LDS[i]);
        seg.upd(arr[i],LIS[i]);
    }
    cout<<ans<<"\n";

}

Compilation message (stderr)

glo.cpp: In function 'void deb2(T&& ...)':
glo.cpp:23:79: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   23 | template<typename... T> void deb2(T&&... args){ if(DEBUG) ((cout<<args<<" "), ...); if(DEBUG) cout<<"\n";}
      |                                                                               ^~~
glo.cpp: In member function 'void SegTree::init(int)':
glo.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int i =0; i<seg.size(); i++) seg[i] = 0;
      |                       ~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25