Submission #785599

#	Time	Username	Problem	Language	Result	Execution time	Memory
785599		devariaota	Global Warming (CEOI18_glo)	C++17	5 / 100	2084 ms	9932 KiB

glo

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

#define int long long

int n, x, t[200005], ans = 0;

int sg[200005];

void build(int index, int l, int r) {
  if (l == r) {
    sg[index] = INT_MIN;
    return;
  }

  int m = (l+r)/2;
  
  build(index*2, l, m);
  build(index*2+1, m+1, r);
  sg[index] = max(sg[index*2], sg[index*2+1]);
}

int query(int index, int l, int r, int x, int y) {
  if (x <= l and y >= r) return sg[index];
  else if ((l < x and r < x) or (l > y and r > y)) return INT_MIN;

  int m = (l+r)/2;
  return max(query(index*2, l, m, x, y), query(index*2+1, m+1, r, x, y));
}


void update(int index, int l, int r, int pos, int val) {
  if (pos < l or pos > r) return;
  else if (l == r) {
    sg[index] = val;
    return;
  }

  int m = (l+r)/2;
  if (pos <= m) {
    update(index*2, l, m, pos, val);
  } else update(index*2+1, m+1, r, pos, val);

  sg[index] = max(sg[index*2], sg[index*2+1]);
}


void solve(int l, int r, int s) {
  // cout << "loop : " << l << " " << r << " " << s << endl;
  map<int, int> maks;
  set<int, greater<int>> memo;
  set<int>::iterator it;
  vector<int> compress;
  map<int, int> idx;
  build(1, 0, n);
  int cur;

  for (int i = l; i <= r; i++) {
    t[i] += s;
    compress.push_back(t[i]);
  }
  for (int i = 0; i < compress.size(); i++) {
    idx[compress[i]] = i;
  }

  stack<int> st;
  int temp, temp2;
  for (int i = 1; i <= n; i++) {
    while (!st.empty()) {
      if (t[i] <= st.top()) st.pop();
      else break;
    }
    st.push(t[i]);
    memo.insert(t[i]);
    temp = st.size();
    // update(1, 0, n, t[i])
    temp2 = query(1, 0, n, idx[t[i]], idx[t[i]]);
    if (temp > temp2) {
      update(1, 0, n, idx[t[i]], temp);
    }
    // maks[t[i]] = max(maks[t[i]], temp);

    // if (memo.size() > 1) {
    //   for (it = memo.begin(); it != memo.end(); it++) {
    //     if ((*it) == t[i]) break;
    //   }
    //   it++;
    //   if (it != memo.end()) {
    //     maks[t[i]] = max(maks[t[i]], maks[*it]+1);  
    //   }
    // }
    // for (it = memo.begin(); it != memo.end(); it++) {
    //   if ((*it) < t[i]) {
    //     maks[t[i]] = max(maks[t[i]], maks[*it]+1);
    //   }
    // }

    update(1, 0, n, idx[t[i]], query(1, 0, n, 0, idx[t[i]]));

    temp = query(1, 0, n, 0, idx[t[i]]);
    // cout << i << " " << t[i] << " " << temp << endl;
    ans = max(temp, ans);
  }

  for (int i = l; i <= r; i++) {
    t[i] -= s;
  }
}

signed main() {
  cin >> n >> x;
  for (int i = 1; i <= n; i++) cin >> t[i];

  if (x == 0) {
    solve(1, n, 0);
    cout << ans << endl;
    return 0;
  }

  for (int l = 1; l <= n; l++) {
    for (int r = l; r <= n; r++) {
      for (int s = -x; s <= x; s++) {
        solve(l, r, s);
      }
    }
  }

  cout << ans << endl;
}

Compilation message (stderr)

glo.cpp: In function 'void solve(long long int, long long int, long long int)':
glo.cpp:62:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i = 0; i < compress.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
glo.cpp:56:7: warning: unused variable 'cur' [-Wunused-variable]
   56 |   int cur;
      |       ^~~

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