oj.uz

Submission #464262

# Submission time Handle Problem Language Result Execution time Memory
464262 2021-08-12T15:52:57 Z Josia Global Warming (CEOI18_glo) C++17
0 / 100
 155 ms 10200 KB 
#include <iostream>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;

#define int int64_t






vector<int> compress(vector<int> a) {
    vector<pair<int, int>> cool;
    
    for (int i = 0; i<a.size(); i++) {
        cool.push_back({a[i], i});
    }
    
    sort(cool.begin(), cool.end());
    
    int last = INT64_MIN;
    int counter = -1;
    
    for (int i = 0; i<a.size(); i++) {
        if (last != cool[i].first) counter++;
        last = cool[i].first;
        cool[i].first = counter;
        swap(cool[i].first, cool[i].second);
    }
    
    sort(cool.begin(), cool.end());

    vector<int> res;
    
    for (auto i: cool) {
        res.push_back(i.second);
    }
    
    return res;
    
}

vector<int> tree;

void update(int v, int rl, int rr, int pos, int x) {
    if (rl == rr) {
        tree[v] = x;
        return;
    }
    
    int rm = (rl + rr) / 2;
    if (pos <= rm) update(v*2, rl, rm, pos, x);
    else update(v*2+1, rm+1, rr, pos, x);
    tree[v] = max(tree[v*2], tree[v*2+1]);
}


int querry(int v, int rl, int rr, int ql, int qr) {
    if (ql > qr) return 0;
    if (rl == ql && rr == qr) return tree[v];
    
    int rm = (rl + rr) / 2;
    return max(querry(v*2, rl, rm, ql, min(qr, rm)), querry(v*2+1, rm+1, rr, max(ql, rm+1), qr));
}



vector<int> lisfast(vector<int> a) {
    tree.assign(a.size()*4, 0);
    
    a = compress(a);
    
    vector<int> dp(a.size());
    dp[0] = 1;
    update(1, 0, a.size()-1, a[0], 1);
    

    for (int i = 1; i<a.size(); i++) {
        dp[i] = max(1 + querry(1, 0, a.size()-1, 0, a[i]-1), dp[i-1]);
        update(1, 0, a.size()-1, a[i], dp[i]);
    }

    return dp;
}


vector<int> ldsfast(vector<int> a) {
    tree.assign(a.size()*4, 0);
    
    
    a = compress(a);


    vector<int> dp(a.size());
    dp[0] = 1;
    update(1, 0, a.size()-1, a[0], 1);
    
    
    for (int i = 1; i<a.size(); i++) {
        dp[i] = max(1 + querry(1, 0, a.size()-1, a[i]+1, a.size()-1), dp[i-1]);
        update(1, 0, a.size()-1, a[i], dp[i]);
    }
    return dp;
}




signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, x; cin >> n >> x;
    
    assert(x == 1e9);
    
    
    vector<int> a(n);
    
    for (int i = 0; i<n; i++) {
        cin >> a[i];
    }
    
    vector<int> fromBeginning = lisfast(a);
    
    reverse(a.begin(), a.end());
    vector<int> fromEnd = ldsfast(a);
    reverse(fromEnd.begin(), fromEnd.end());
    
//    for (int i: fromBeginning) cout << i << " ";
//    cout << "\n";
//    for (int i: fromEnd) cout << i << " ";
//    cout << "\n";

    int res = 0;
    for (int i = 0; i<n-1; i++) {
        if (fromBeginning[i] + fromEnd[i+1] > res) res = fromBeginning[i] + fromEnd[i];
    }
    if (fromBeginning[n-1] > res) res = fromBeginning[n-1];

    cout << res << "\n";
    

    return 0;
}

Compilation message

glo.cpp: In function 'std::vector<long int> compress(std::vector<long int>)':
glo.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i<a.size(); i++) {
      |                     ~^~~~~~~~~
glo.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i<a.size(); i++) {
      |                     ~^~~~~~~~~
glo.cpp: In function 'std::vector<long int> lisfast(std::vector<long int>)':
glo.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 1; i<a.size(); i++) {
      |                     ~^~~~~~~~~
glo.cpp: In function 'std::vector<long int> ldsfast(std::vector<long int>)':
glo.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 1; i<a.size(); i++) {
      |                     ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -