답안 #248564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248564	2020-07-12T18:14:48 Z	Sprdalo	Global Warming (CEOI18_glo)	C++17	100 / 100	535 ms	38296 KB

#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

template<int MAXN>
struct segtr{
    //To change the purpose of the segtree just redefine the operators
    struct node{
        int x;
        node(int x = 0) : x(x) {}
        node& operator+= (const node& other){
            x = max(x, other.x);
            return *this;
        }
        node operator+ (const node& other){
            node tmp = *this;
            return tmp += other;
        }
    };
    
    node a[2*MAXN];
    
    //Initialize the array
    void init(){
        for(int i = 1; i <= MAXN; ++i){
            a[i+MAXN-1] = node{};
        }
        for(int i = MAXN-1; i > 0; --i){
            a[i] = a[2*i] + a[2*i+1];
        }
    }
    
    //Sets the node and updates the tree
    void set(int pos, node val){
        pos += MAXN-1;
        a[pos] = val;
        
        while(pos > 1){
            pos /= 2;
            a[pos] = a[2*pos] + a[2*pos+1];
        }
    }
    inline void add(int pos, node val){ //Just forwards to set
        set(pos, node{a[pos+MAXN-1]+val});
    }
    
    //Gets the range query
    node get(int l, int r, int pos = 1, int rl = 1, int rr = MAXN){
        if(r < rl || rr < l){ return node{}; }
        if(l <= rl && rr <= r){ return a[pos]; }
        
        int rm = (rl+rr)/2;
        return get(l, r, 2*pos, rl, rm) + get(l, r, 2*pos+1, rm+1, rr);
    }
    
};
segtr<131072*2> drvo;

vi a, lds, c;
int n, x, sol = 1;

void init(){
    vi tmp = a;
    reverse(tmp.begin(), tmp.end());
    for (auto& i : tmp)
        i *= -1;

    vi v(n + 1, INT32_MAX);
    v[0] = INT32_MIN;

    for (int i = 0; i < n; ++i){
        int y = tmp[i], ind = lower_bound(v.begin(), v.end(), y) - v.begin();

        v[ind] = y;
        lds[i] = ind;
    }

    reverse(lds.begin(), lds.end());
}

unordered_map<int, int> mapa;
set<int> st;
void kompresuj(){
    mapa.reserve(131072 * 2);
    mapa.max_load_factor(0.25);

    int cur = 0;
    for (auto& i : st){
        mapa[i] = ++cur;
    }

    for (int i = 0; i < n; ++i)
        c[i] = mapa[a[i]];
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);

    cin >> n >> x;
    a = vi(n, 0);
    for (auto& i : a){
        cin >> i;
        st.insert(i);
    }

    lds = vi(n, 0);
    init();
    c = vi(n, 0);
    kompresuj();

    vi b(n + 1, INT32_MAX);
    b[0] = INT32_MIN;
    for (int i = 0; i < n; ++i){

        int ind = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        sol = max(sol, ind);
        b[ind] = a[i];

        int res = lds[i];
        //treba mi lis:. se zavrsava u < a[i] + x
        //odnosno nadjes u st zadnji broj koji je manji od a[i] + x
        //ako ne postoji skip
        //ako postoji nadjes ga u c
        //i vratis get(1, c);

        auto it = st.lower_bound(a[i] + x);
        if (it == st.begin()){
            drvo.add(c[i], ind);
            continue;
        }
        --it;
        int y = mapa[*it];

        res += drvo.get(1, y).x;
 //       cout << res << endl;
        sol = max(sol, res);
        drvo.add(c[i], ind);
    }

   // for (auto& i : lds)
     //   cout << i << ' ';

    cout << sol << '\n';
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6656 KB	Output is correct
2	Correct	3 ms	6656 KB	Output is correct
3	Correct	3 ms	6656 KB	Output is correct
4	Correct	3 ms	6656 KB	Output is correct
5	Correct	3 ms	6656 KB	Output is correct
6	Correct	3 ms	6656 KB	Output is correct
7	Correct	3 ms	6656 KB	Output is correct
8	Correct	3 ms	6656 KB	Output is correct
9	Correct	3 ms	6656 KB	Output is correct
10	Correct	3 ms	6656 KB	Output is correct
11	Correct	3 ms	6656 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6656 KB	Output is correct
2	Correct	3 ms	6656 KB	Output is correct
3	Correct	3 ms	6656 KB	Output is correct
4	Correct	3 ms	6656 KB	Output is correct
5	Correct	3 ms	6656 KB	Output is correct
6	Correct	3 ms	6656 KB	Output is correct
7	Correct	3 ms	6656 KB	Output is correct
8	Correct	3 ms	6656 KB	Output is correct
9	Correct	3 ms	6656 KB	Output is correct
10	Correct	3 ms	6656 KB	Output is correct
11	Correct	3 ms	6656 KB	Output is correct
12	Correct	5 ms	6656 KB	Output is correct
13	Correct	3 ms	6656 KB	Output is correct
14	Correct	3 ms	6656 KB	Output is correct
15	Correct	4 ms	6656 KB	Output is correct
16	Correct	4 ms	6656 KB	Output is correct
17	Correct	3 ms	6656 KB	Output is correct
18	Correct	3 ms	6656 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6656 KB	Output is correct
2	Correct	3 ms	6656 KB	Output is correct
3	Correct	3 ms	6656 KB	Output is correct
4	Correct	3 ms	6656 KB	Output is correct
5	Correct	3 ms	6656 KB	Output is correct
6	Correct	3 ms	6656 KB	Output is correct
7	Correct	3 ms	6656 KB	Output is correct
8	Correct	3 ms	6656 KB	Output is correct
9	Correct	3 ms	6656 KB	Output is correct
10	Correct	3 ms	6656 KB	Output is correct
11	Correct	3 ms	6656 KB	Output is correct
12	Correct	5 ms	6656 KB	Output is correct
13	Correct	3 ms	6656 KB	Output is correct
14	Correct	3 ms	6656 KB	Output is correct
15	Correct	4 ms	6656 KB	Output is correct
16	Correct	4 ms	6656 KB	Output is correct
17	Correct	3 ms	6656 KB	Output is correct
18	Correct	3 ms	6656 KB	Output is correct
19	Correct	4 ms	6784 KB	Output is correct
20	Correct	4 ms	6784 KB	Output is correct
21	Correct	4 ms	6784 KB	Output is correct
22	Correct	4 ms	6784 KB	Output is correct
23	Correct	4 ms	6656 KB	Output is correct
24	Correct	4 ms	6656 KB	Output is correct
25	Correct	4 ms	6656 KB	Output is correct
26	Correct	4 ms	6784 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	480 ms	38264 KB	Output is correct
2	Correct	494 ms	38208 KB	Output is correct
3	Correct	465 ms	38212 KB	Output is correct
4	Correct	474 ms	38212 KB	Output is correct
5	Correct	156 ms	24128 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	12648 KB	Output is correct
2	Correct	84 ms	12648 KB	Output is correct
3	Correct	95 ms	12648 KB	Output is correct
4	Correct	37 ms	10472 KB	Output is correct
5	Correct	5 ms	6656 KB	Output is correct
6	Correct	36 ms	10472 KB	Output is correct
7	Correct	63 ms	12672 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	21208 KB	Output is correct
2	Correct	119 ms	21208 KB	Output is correct
3	Correct	282 ms	38296 KB	Output is correct
4	Correct	149 ms	24136 KB	Output is correct
5	Correct	80 ms	20844 KB	Output is correct
6	Correct	161 ms	36832 KB	Output is correct
7	Correct	158 ms	37472 KB	Output is correct
8	Correct	102 ms	21208 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6656 KB	Output is correct
2	Correct	3 ms	6656 KB	Output is correct
3	Correct	3 ms	6656 KB	Output is correct
4	Correct	3 ms	6656 KB	Output is correct
5	Correct	3 ms	6656 KB	Output is correct
6	Correct	3 ms	6656 KB	Output is correct
7	Correct	3 ms	6656 KB	Output is correct
8	Correct	3 ms	6656 KB	Output is correct
9	Correct	3 ms	6656 KB	Output is correct
10	Correct	3 ms	6656 KB	Output is correct
11	Correct	3 ms	6656 KB	Output is correct
12	Correct	5 ms	6656 KB	Output is correct
13	Correct	3 ms	6656 KB	Output is correct
14	Correct	3 ms	6656 KB	Output is correct
15	Correct	4 ms	6656 KB	Output is correct
16	Correct	4 ms	6656 KB	Output is correct
17	Correct	3 ms	6656 KB	Output is correct
18	Correct	3 ms	6656 KB	Output is correct
19	Correct	4 ms	6784 KB	Output is correct
20	Correct	4 ms	6784 KB	Output is correct
21	Correct	4 ms	6784 KB	Output is correct
22	Correct	4 ms	6784 KB	Output is correct
23	Correct	4 ms	6656 KB	Output is correct
24	Correct	4 ms	6656 KB	Output is correct
25	Correct	4 ms	6656 KB	Output is correct
26	Correct	4 ms	6784 KB	Output is correct
27	Correct	480 ms	38264 KB	Output is correct
28	Correct	494 ms	38208 KB	Output is correct
29	Correct	465 ms	38212 KB	Output is correct
30	Correct	474 ms	38212 KB	Output is correct
31	Correct	156 ms	24128 KB	Output is correct
32	Correct	90 ms	12648 KB	Output is correct
33	Correct	84 ms	12648 KB	Output is correct
34	Correct	95 ms	12648 KB	Output is correct
35	Correct	37 ms	10472 KB	Output is correct
36	Correct	5 ms	6656 KB	Output is correct
37	Correct	36 ms	10472 KB	Output is correct
38	Correct	63 ms	12672 KB	Output is correct
39	Correct	121 ms	21208 KB	Output is correct
40	Correct	119 ms	21208 KB	Output is correct
41	Correct	282 ms	38296 KB	Output is correct
42	Correct	149 ms	24136 KB	Output is correct
43	Correct	80 ms	20844 KB	Output is correct
44	Correct	161 ms	36832 KB	Output is correct
45	Correct	158 ms	37472 KB	Output is correct
46	Correct	102 ms	21208 KB	Output is correct
47	Correct	196 ms	21232 KB	Output is correct
48	Correct	206 ms	21208 KB	Output is correct
49	Correct	535 ms	38208 KB	Output is correct
50	Correct	155 ms	24136 KB	Output is correct
51	Correct	116 ms	22288 KB	Output is correct
52	Correct	192 ms	37704 KB	Output is correct
53	Correct	163 ms	37644 KB	Output is correct
54	Correct	161 ms	38216 KB	Output is correct
55	Correct	320 ms	38208 KB	Output is correct

답안 #248564

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