Submission #477113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477113	2021-09-30T15:06:27 Z	julian33	Global Warming (CEOI18_glo)	C++14	100 / 100	383 ms	13728 KB

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=4e5+5; //make sure this is right
const int mod=1e9+7;

struct RANK{
    vector<int> all;
    int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
    void add(int x){all.pb(x);}
    void fix(){
        sort(all.begin(),all.end());
        all.resize(unique(all.begin(),all.end())-all.begin());
    }  
} rnk;

struct TREE{
    int st[4*mxN];

    void update(int v,int l,int r,int ind,int val){
        if(l>ind || r<ind) return;
        if(l==r){
            maxa(st[v],val);
        } else{
            int m=(l+r)>>1;
            update(v<<1,l,m,ind,val);
            update(v<<1|1,m+1,r,ind,val);
            st[v]=max(st[v<<1],st[v<<1|1]);
        }
    }

    int query(int v,int l,int r,int lq,int rq){
        if(lq>rq)
            return 0;
        if(l>=lq && r<=rq){
            return st[v];
        }
        int m=(l+r)>>1;
        return max(query(v<<1,l,m,lq,min(m,rq)),query(v<<1|1,m+1,r,max(lq,m+1),rq));
    }
} tree1,tree2;  

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n,x; cin>>n>>x;
    vector<int> a(n),lis(n);
    for(int &i:a){
        cin>>i;
        rnk.add(i);
        rnk.add(i-x);
    }
    rnk.fix();
    int ans=0;
    int m=sz(rnk.all);
    for(int i=n-1;i>=0;i--){
        int lo=rnk.get(a[i]-x);
        a[i]=rnk.get(a[i]);
        int lis=tree1.query(1,1,m,a[i]+1,m);
        int use=max(tree1.query(1,1,m,lo+1,m),tree2.query(1,1,m,a[i]+1,m));
        maxa(ans,use+1);
        tree1.update(1,1,m,a[i],lis+1);
        tree2.update(1,1,m,a[i],use+1);
    }
    cout<<ans<<"\n";
}

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	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 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	332 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	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 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	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	320 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	204 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	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 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	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	320 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	1 ms	332 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	2 ms	332 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	339 ms	9624 KB	Output is correct
2	Correct	321 ms	9612 KB	Output is correct
3	Correct	315 ms	9632 KB	Output is correct
4	Correct	312 ms	9660 KB	Output is correct
5	Correct	170 ms	6708 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	3780 KB	Output is correct
2	Correct	67 ms	3784 KB	Output is correct
3	Correct	87 ms	3776 KB	Output is correct
4	Correct	38 ms	2484 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	41 ms	2500 KB	Output is correct
7	Correct	56 ms	3744 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	5144 KB	Output is correct
2	Correct	170 ms	5044 KB	Output is correct
3	Correct	363 ms	9708 KB	Output is correct
4	Correct	169 ms	6824 KB	Output is correct
5	Correct	124 ms	4632 KB	Output is correct
6	Correct	169 ms	8780 KB	Output is correct
7	Correct	188 ms	9420 KB	Output is correct
8	Correct	117 ms	5056 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	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 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	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	320 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	1 ms	332 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	2 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	339 ms	9624 KB	Output is correct
28	Correct	321 ms	9612 KB	Output is correct
29	Correct	315 ms	9632 KB	Output is correct
30	Correct	312 ms	9660 KB	Output is correct
31	Correct	170 ms	6708 KB	Output is correct
32	Correct	82 ms	3780 KB	Output is correct
33	Correct	67 ms	3784 KB	Output is correct
34	Correct	87 ms	3776 KB	Output is correct
35	Correct	38 ms	2484 KB	Output is correct
36	Correct	1 ms	204 KB	Output is correct
37	Correct	41 ms	2500 KB	Output is correct
38	Correct	56 ms	3744 KB	Output is correct
39	Correct	146 ms	5144 KB	Output is correct
40	Correct	170 ms	5044 KB	Output is correct
41	Correct	363 ms	9708 KB	Output is correct
42	Correct	169 ms	6824 KB	Output is correct
43	Correct	124 ms	4632 KB	Output is correct
44	Correct	169 ms	8780 KB	Output is correct
45	Correct	188 ms	9420 KB	Output is correct
46	Correct	117 ms	5056 KB	Output is correct
47	Correct	165 ms	7044 KB	Output is correct
48	Correct	156 ms	7092 KB	Output is correct
49	Correct	383 ms	13728 KB	Output is correct
50	Correct	169 ms	8848 KB	Output is correct
51	Correct	123 ms	6452 KB	Output is correct
52	Correct	186 ms	8928 KB	Output is correct
53	Correct	177 ms	9092 KB	Output is correct
54	Correct	177 ms	9628 KB	Output is correct
55	Correct	275 ms	13648 KB	Output is correct

Submission #477113

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0