Submission #233068

#	Time	Username	Problem	Language	Result	Execution time	Memory
233068		AlexLuchianov	Global Warming (CEOI18_glo)	C++14	100 / 100	579 ms	25144 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <map>

using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int v[1 + nmax];
map<int,int> mp;

class FenwickTree{
private:
  vector<int> aib;
  int n;
public:
  FenwickTree(int n_){
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val){
    for(int x = pos; x <= n; x += (x & (x ^ (x - 1))))
      aib[x] = max(aib[x], val);
  }
  int query(int pos){
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result = max(result, aib[x]);
    return result;
  }
};

void normalize(int n, int lim){
  vector<int> temp;
  for(int i = 1; i <= n; i++) {
    temp.push_back(v[i]);
    temp.push_back(v[i] + lim);
  }
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++)
    mp[temp[i]] = 1 + i;
}


int main()
{
  int n, lim;
  cin >> n >> lim;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  normalize(n, lim);
  FenwickTree basic(1 + 2 * n), advanced(1 + 2 * n);
  for(int i = 1;i <= n; i++){
    int id1 = mp[v[i]];
    int id2 = mp[v[i] + lim];
    advanced.update(id2, max(basic.query(id2 - 1), advanced.query(id2 - 1)) + 1);
    basic.update(id1, basic.query(id1 - 1) + 1);
  }
  cout << advanced.query(2 * n);
  return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void normalize(int, int)':
glo.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~

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