oj.uz

Submission #518462

# Submission time Handle Problem Language Result Execution time Memory
518462 2022-01-23T21:10:43 Z Yazan_Alattar Global Warming (CEOI18_glo) C++14
37 / 100
 547 ms 45588 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 300007;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int n, x, a[M], pref[M], suf[M], last[M], seg[32 * M], L[32 * M], R[32 * M], ans, nodesNum = 1;
map <int,int> lastocur;

void upd(int pos, int v, int node = 1, int l = 1, int r = 1e9)
{
    if(l == r){
        seg[node] = v;
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        if(!L[node]) L[node] = ++nodesNum;
        upd(pos, v, L[node], l, mid);
   }
    else{
        if(!R[node]) R[node] = ++nodesNum;
        upd(pos, v, R[node], mid + 1, r);
    }
    seg[node] = max(seg[L[node]], seg[R[node]]);
    return;
}

int get(int st, int en, int node = 1, int l = 1, int r = 1e9)
{
    if(l > en || r < st) return -inf;
    if(l >= st && r <= en) return seg[node];
    if(!L[node]) L[node] = ++nodesNum;
    if(!R[node]) R[node] = ++nodesNum;
    int mid = (l + r) / 2;
    return max(get(st, en, L[node], l, mid), get(st, en, R[node], mid + 1, r));
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    vector <int> lis;
    for(int i = 1; i <= n; ++i){
        int it = lower_bound(all(lis), a[i]) - lis.begin();
        if(it == lis.size()) lis.pb(a[i]);
        else lis[it] = a[i];
        pref[i] = it + 1;
    }
    lis.clear();
    for(int i = n; i; --i){
        int it = lower_bound(all(lis), - a[i]) - lis.begin();
        if(it == lis.size()) lis.pb(-a[i]);
        else lis[it] = -a[i];
        suf[i] = it  + 1;
        upd(a[i], it + 1);
        if(lastocur[a[i]]) last[i] = lastocur[a[i]];
        lastocur[a[i]] = i;
    }
    for(int i = 1; i <= n; ++i){
        upd(a[i], suf[last[i]]);
        ans = max(ans, pref[i] + get(a[i] - x + 1, a[i] + x - 1));
    }
    cout << ans << endl;
    return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if(it == lis.size()) lis.pb(a[i]);
      |            ~~~^~~~~~~~~~~~~
glo.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if(it == lis.size()) lis.pb(-a[i]);
      |            ~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 547 ms 43688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 20228 KB Output is correct
2 Correct 115 ms 20648 KB Output is correct
3 Correct 112 ms 20720 KB Output is correct
4 Correct 57 ms 11552 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 48 ms 3564 KB Output is correct
7 Correct 77 ms 15404 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 23148 KB Output is correct
2 Correct 202 ms 24056 KB Output is correct
3 Correct 518 ms 45588 KB Output is correct
4 Correct 173 ms 26580 KB Output is correct
5 Correct 79 ms 9288 KB Output is correct
6 Correct 140 ms 17476 KB Output is correct
7 Correct 171 ms 18216 KB Output is correct
8 Correct 131 ms 19172 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -