Submission #397478

#	Time	Username	Problem	Language	Result	Execution time	Memory
397478		ollel	Global Warming (CEOI18_glo)	C++14	38 / 100	548 ms	15288 KiB

glo

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef long long ll;

class SegTree {
public:
  vi tr; int n;

  int l(int x) {return (x<<1);}
  int r(int x) {return (x<<1)|1;}

  int combine(int a, int b) {return max(a, b);}

  void build(int i, int L, int R, vi& arr) {
    if (L == R) tr[i] = arr[L];
    else {
      int mid = (L + R) / 2;
      build(l(i), L, mid, arr);
      build(r(i), mid + 1, R, arr);
      tr[i] = combine(tr[l(i)], tr[r(i)]);
    }
  }

  void build(vi &arr) {
    build(1, 0, n - 1, arr);
  }

  SegTree(vi &arr) {
    n = arr.size();
    tr.resize(4*n);
    this->build(arr);
  }

  int query(int i, int a, int b, int L, int R) {
    if (b < a) return 0;
    if (L > b || R < a) return 0;
    if (L >= a && R <= b) return tr[i];
    int mid = (L + R) / 2;
    return combine(
      query(l(i), a, b, L, mid),
      query(r(i), a, b, mid + 1, R));
  }

  int query(int i, int j) {
    return query(1, i, j, 0, n - 1);
  }

  void update(int i, int a, int L, int R, int v) {
    if (a < L || a > R) return;
    if (L == R) {tr[i] = v; return;}
    int mid = (L + R) / 2;
    update(l(i), a, L, mid, v);
    update(r(i), a, mid + 1, R, v);
    tr[i] = combine(tr[l(i)], tr[r(i)]);
  }

  void update(int i, int v) {
    update(1, i, 0, n - 1, v);
  }
};

int n, x;
vi arr;

int test(vi&arr) {
  vi vals(n);
  map<int,int> cmpr;
  rep(i,0,n) vals[i] = arr[i];
  sort(vals.begin(), vals.end());
  rep(i,0,n) {
    if (cmpr.find(vals[i]) == cmpr.end()) cmpr.insert({vals[i], i});
  }

  vi trarr(n, 0);
  SegTree st(trarr);

  rep(i,0,n) {
    int V = cmpr[arr[i]];
    int ans = st.query(0, V - 1) + 1;
    if (st.query(V, V) < ans) st.update(V, ans);
  }

  return st.query(0, n - 1);
}

int main()
{
  cin >> n >> x;
  arr.resize(n);
  rep(i,0,n) cin>>arr[i];

  if (n > 10000) {
    int ans = test(arr);
    cout << ans;
  } else {
    int ans = test(arr);

    rep(end, 0, n) {
      arr[end] -= x;
      ans = max(ans, test(arr));
    }

    cout << ans;
  }
}

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