oj.uz

Submission #525186

# Submission time Handle Problem Language Result Execution time Memory
525186 2022-02-11T04:09:19 Z Maillew Global Warming (CEOI18_glo) C++14
100 / 100
 291 ms 18116 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 18004 KB Output is correct
2 Correct 280 ms 18036 KB Output is correct
3 Correct 268 ms 17980 KB Output is correct
4 Correct 285 ms 18068 KB Output is correct
5 Correct 142 ms 17256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4760 KB Output is correct
2 Correct 58 ms 4756 KB Output is correct
3 Correct 61 ms 4972 KB Output is correct
4 Correct 33 ms 4612 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 34 ms 4552 KB Output is correct
7 Correct 48 ms 4784 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9236 KB Output is correct
2 Correct 121 ms 9316 KB Output is correct
3 Correct 291 ms 17984 KB Output is correct
4 Correct 144 ms 17216 KB Output is correct
5 Correct 71 ms 8876 KB Output is correct
6 Correct 124 ms 16448 KB Output is correct
7 Correct 127 ms 17172 KB Output is correct
8 Correct 102 ms 9204 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 277 ms 18004 KB Output is correct
28 Correct 280 ms 18036 KB Output is correct
29 Correct 268 ms 17980 KB Output is correct
30 Correct 285 ms 18068 KB Output is correct
31 Correct 142 ms 17256 KB Output is correct
32 Correct 59 ms 4760 KB Output is correct
33 Correct 58 ms 4756 KB Output is correct
34 Correct 61 ms 4972 KB Output is correct
35 Correct 33 ms 4612 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 34 ms 4552 KB Output is correct
38 Correct 48 ms 4784 KB Output is correct
39 Correct 108 ms 9236 KB Output is correct
40 Correct 121 ms 9316 KB Output is correct
41 Correct 291 ms 17984 KB Output is correct
42 Correct 144 ms 17216 KB Output is correct
43 Correct 71 ms 8876 KB Output is correct
44 Correct 124 ms 16448 KB Output is correct
45 Correct 127 ms 17172 KB Output is correct
46 Correct 102 ms 9204 KB Output is correct
47 Correct 122 ms 9200 KB Output is correct
48 Correct 125 ms 9264 KB Output is correct
49 Correct 267 ms 18116 KB Output is correct
50 Correct 142 ms 17156 KB Output is correct
51 Correct 115 ms 12988 KB Output is correct
52 Correct 173 ms 17424 KB Output is correct
53 Correct 130 ms 17332 KB Output is correct
54 Correct 135 ms 17972 KB Output is correct
55 Correct 221 ms 18028 KB Output is correct