Submission #638221

#	Time	Username	Problem	Language	Result	Execution time	Memory
638221		Neos	Global Warming (CEOI18_glo)	C++14	17 / 100	251 ms	12196 KiB

glo

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 3e5 + 7, oo = 1e9 + 7;

int n, m, ans, a[N], T[4 * N], lis[N], lds[N];

void upd(int id, int l, int r, int pos, int val) {
    if (l > pos || r < pos) return;
    if (l == r) {
        maximize(T[id], val);
        return;
    }

    int mid = l + r >> 1, k = id << 1;
    upd(k, l, mid, pos, val); upd(k | 1, mid + 1, r, pos, val);
    T[id] = max(T[k], T[k | 1]);
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return -oo;
    if (u <= l && r <= v) return T[id];

    int mid = l + r >> 1, k = id << 1;
    return max(get(k, l, mid, u, v), get(k | 1, mid + 1, r, u, v));
}

int get(int l, int r) {
    return get(1, 1, N - 1, l, r);
}

void upd(int pos, int val) {
    upd(1, 1, N - 1, pos, val);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("test.inp", "r")) 
	freopen("test.inp", "r", stdin);
    cin >> n >> m; vector<int> v(1, m), vec;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = -1; j <= 1; j++)
            v.push_back(a[i] + j * m + abs(j));
    }
     
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());

    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        int pos = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
        if (pos == vec.size()) vec.push_back(a[i]); else vec[pos] = a[i];
        lis[i] = pos + 1; 
    }
    
    vec.clear();
    for (int i = n; i >= 1; i--) {      
        int pos = lower_bound(vec.begin(), vec.end(), -a[i]) - vec.begin();
        if (pos == vec.size()) vec.push_back(-a[i]); else vec[pos] = -a[i];
        lds[i] = pos + 1;
    }

    for (int i = n; i >= 1; i--) {
        int val = lower_bound(v.begin(), v.end(), a[i] - m + 1) - v.begin() + 1;
        maximize(ans, lis[i] + get(val, N - 1));
        upd(a[i], lds[i]);
    }

    memset(T, 0, sizeof T);
    for (int i = 1; i <= n; i++) {
        int val = lower_bound(v.begin(), v.end(), a[i] + m + 1) - v.begin() + 1;
        maximize(ans, lds[i] + get(val, N - 1));
  //      cerr << i << ' ' << lds[i] << ' ' << get(val, N - 1) << endl;
        upd(a[i], lis[i]);
    }    
    cout << ans;
}

Compilation message (stderr)

glo.cpp: In function 'void upd(int, int, int, int, int)':
glo.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1, k = id << 1;
      |               ~~^~~
glo.cpp: In function 'int get(int, int, int, int, int)':
glo.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1, k = id << 1;
      |               ~~^~~
glo.cpp: In function 'int main()':
glo.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         if (pos == vec.size()) vec.push_back(a[i]); else vec[pos] = a[i];
      |             ~~~~^~~~~~~~~~~~~
glo.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if (pos == vec.size()) vec.push_back(-a[i]); else vec[pos] = -a[i];
      |             ~~~~^~~~~~~~~~~~~
glo.cpp:53:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  freopen("test.inp", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25