oj.uz

Submission #166133

# Submission time Handle Problem Language Result Execution time Memory
166133 2019-11-30T21:57:21 Z GustavK Global Warming (CEOI18_glo) C++14
28 / 100
 2000 ms 8752 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 1000000007;
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())

int LIS(vl a){
    vl b(200010, linf);
    int r = 0;
    for(int i = 0; i < sz(a); i++){
        auto p = lower_bound(all(b), a[i]);
        if(*p == linf) r++;
        *p = a[i];
    }
    return r;
}

vl A;
int dp[100000];
int LIS2(int pos){
    if(dp[pos] != -1) return dp[pos];
    int r = 0;
    for(int i = pos+1; i < sz(A); i++){
        if(A[i] > A[pos])
            r = max(r, LIS2(i));
    }
    return dp[pos] = r + 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, x;
    cin >> n >> x;
    vl a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    vl b(200010, linf);
    stack<pair<ll,ll>> undo;
    for(int i = n-1; i >= 0; i--){
        int p = lower_bound(all(b), -a[i]-x) - b.begin();
        undo.emplace(p, b[p]);
        b[p] = -a[i]-x;
    }

    vl c(200010, linf);
    int len = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
        b[undo.top().first] = undo.top().second;
        undo.pop();

        int p = lower_bound(all(c), a[i]) - c.begin();
        if(c[p] == linf) len++;
        if(p+1 == len){
            ans = max(ans, len + (int)(lower_bound(all(b), -a[i]) - b.begin()));
        }
        c[p] = a[i];
    }

    if(1){
        ans = 0;
        for(int i = n-1; i >= 0; i--){
            a[i] += x;
            ans = max(ans, LIS(a));
        }
    }

    cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5084 KB Output is correct
4 Correct 7 ms 5080 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5116 KB Output is correct
9 Correct 19 ms 5112 KB Output is correct
10 Correct 7 ms 5080 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5084 KB Output is correct
4 Correct 7 ms 5080 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5116 KB Output is correct
9 Correct 19 ms 5112 KB Output is correct
10 Correct 7 ms 5080 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 12 ms 5112 KB Output is correct
13 Correct 12 ms 5112 KB Output is correct
14 Correct 12 ms 5112 KB Output is correct
15 Correct 13 ms 5208 KB Output is correct
16 Correct 12 ms 5112 KB Output is correct
17 Correct 8 ms 5080 KB Output is correct
18 Correct 9 ms 5084 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5084 KB Output is correct
4 Correct 7 ms 5080 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5116 KB Output is correct
9 Correct 19 ms 5112 KB Output is correct
10 Correct 7 ms 5080 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 12 ms 5112 KB Output is correct
13 Correct 12 ms 5112 KB Output is correct
14 Correct 12 ms 5112 KB Output is correct
15 Correct 13 ms 5208 KB Output is correct
16 Correct 12 ms 5112 KB Output is correct
17 Correct 8 ms 5080 KB Output is correct
18 Correct 9 ms 5084 KB Output is correct
19 Correct 167 ms 5240 KB Output is correct
20 Correct 166 ms 5152 KB Output is correct
21 Correct 173 ms 5084 KB Output is correct
22 Correct 164 ms 5112 KB Output is correct
23 Correct 168 ms 5112 KB Output is correct
24 Correct 167 ms 5180 KB Output is correct
25 Correct 150 ms 5120 KB Output is correct
26 Correct 170 ms 5120 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 8752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 6040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 6828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5084 KB Output is correct
4 Correct 7 ms 5080 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5116 KB Output is correct
9 Correct 19 ms 5112 KB Output is correct
10 Correct 7 ms 5080 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 12 ms 5112 KB Output is correct
13 Correct 12 ms 5112 KB Output is correct
14 Correct 12 ms 5112 KB Output is correct
15 Correct 13 ms 5208 KB Output is correct
16 Correct 12 ms 5112 KB Output is correct
17 Correct 8 ms 5080 KB Output is correct
18 Correct 9 ms 5084 KB Output is correct
19 Correct 167 ms 5240 KB Output is correct
20 Correct 166 ms 5152 KB Output is correct
21 Correct 173 ms 5084 KB Output is correct
22 Correct 164 ms 5112 KB Output is correct
23 Correct 168 ms 5112 KB Output is correct
24 Correct 167 ms 5180 KB Output is correct
25 Correct 150 ms 5120 KB Output is correct
26 Correct 170 ms 5120 KB Output is correct
27 Execution timed out 2057 ms 8752 KB Time limit exceeded
28 Halted 0 ms 0 KB -