Submission #436887

#	Time	Username	Problem	Language	Result	Execution time	Memory
436887		vulpes2	Financial Report (JOI21_financial)	C++17	100 / 100	1314 ms	55500 KiB

Main

//#include <atcoder/maxflow.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 

#include <iostream>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iterator>
#include <random>
#include <chrono>
#include <complex>
#include <bitset>
#include <fstream>
 
 
#define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
#define set_map_includes(set, elt) (set.find((elt)) != set.end())
#define readint(i) int i; cin >> i
#define readll(i) ll i; cin >> i
#define readdouble(i) double i; cin >> i
#define readstring(s) string s; cin >> s

typedef long long ll;

 
//using namespace __gnu_pbds;
//using namespace atcoder;
using namespace std;

const ll modd = (1000LL * 1000LL * 1000LL + 7LL);
//const ll modd = 998244353;

template<class T>
class SegmentTree2 {
    public:
     
      SegmentTree2(const vector<T>& data, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) {   
          Initialize(data);
      }

      SegmentTree2(int n, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) {
          vector<T> temp(n, zv);
          Initialize(temp);
      }

      T operator[](int i) {
          return tree[B+i];
      }

      T GetEvaluation(int L, int R) {   // "min/max" on interval [L,R); 0-based indexing, as usual
        if (R<=L) {  return zv;  }
        return GetEvaluationHelper(L, R, 0, B, 1);
      }


      void SetVal(int i, T val) {
			tree[B+i] = val;
			for(int j = (B + i) / 2; j >= 1; j /= 2) {
				tree[j] = f(tree[2*j], tree[2*j+1]);
			}
      }

      private:
        vector<T> tree;
        int B;  // power of two greater than size of input data
        T zv;
        function<T(T,T)> f;

        void Initialize(const vector<T>& data) {
    	  B = 1;
          while(B < data.size()) {B *= 2;  }
          tree = std::move(vector<T>(2*B, zv));
          copy(data.begin(), data.end(), next(tree.begin(), B));
          for(int i = B - 1; i >= 1; --i) {
  	  	     tree[i] = f(tree[2*i], tree[2*i+1]);
          }
        }

      T GetEvaluationHelper(int L, int R, int start, int length, int tree_index) {
          if (L==R) {  return zv; }
          if ((L==start) && (R==start+length)) {   return tree[tree_index];  }
          int midpoint = start + length/2;

          T left_ = zv, right_ = zv;
          if (L<=min(midpoint,R)) {
            left_ = GetEvaluationHelper(L, min(midpoint,R), start, length/2, 2*tree_index);
          }
          if (max(midpoint,L)<=R) {
            right_ = GetEvaluationHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1);
          }
          return f(left_, right_);
      }

};


class block_correct {
    public:
      vector<bool> occupied;
      int dd;
 
      block_correct(int n, int d) : occupied(n, false), dd(d) {}

      void print() {
          for(auto x : occupied) {
              cout << (x ? "1" : "0");
          }
          cout << endl;
      }
 
      void add(int i) {
          occupied[i] = true;
      }
 
      int upto(int i) {
          forr(j,i,occupied.size()) {
              if (j+dd>occupied.size()) { break; }
              bool occ = true;
              forr(k,j,dd) {
                  occ &= occupied[k];
              }
              if (occ) {
                  return j+dd;
              }
          }
          return occupied.size();
      }
 
};

class block {
    public:
      set<pair<int,int>> intervals;
      set<int> obstacle_begin;
      int d;
      int n;

      block(int nn, int dd) : n(nn), d(dd) {}

      void print() {
          for(auto x : intervals) {
              cout << x.first << "," << x.second << "; ";
          }
          cout << "!!";
          cout << endl;
      }

      void add(int i) {
          auto it = intervals.lower_bound(make_pair(i,i));
          bool merge_right = ((it!=intervals.end()) && (it->first==i+1));
          bool merge_left = ((it!=intervals.begin()) && (prev(it)->second==i));
          if ((!merge_left) && (!merge_right)) {
              intervals.insert(make_pair(i, i+1));
              if (1>=d) obstacle_begin.insert(i);
          }
          if ((!merge_left) && (merge_right)) {
              int r = it->second;
              intervals.erase(it);
              intervals.insert(make_pair(i, r));
              if (r-i>=d) obstacle_begin.insert(i);
          }
          if ((merge_left) && (!merge_right)) {
              int l = prev(it)->first;
              intervals.erase(prev(it));
              intervals.insert(make_pair(l, i+1));
              if (i+1-l>=d) obstacle_begin.insert(l);
          }
          if ((merge_left) && (merge_right)) {
              int l = prev(it)->first;
              int r = it->second;
              it = intervals.erase(it);
              intervals.erase(prev(it));
              intervals.insert(make_pair(l, r));
              if (r-l>=d) obstacle_begin.insert(l);
          }
      }

      int upto(int i) {
          auto it = obstacle_begin.lower_bound(i);
          if (it==obstacle_begin.end()) {  return n; }
          return *it+d;
      }

};

int main(int argc, char *argv[])   {

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> rand_gen(0, modd);   // rand_gen(rng) gets the rand no

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cout.precision(12);

//    readint(test_cases);
    int test_cases = 1;
    forr(t, 1, test_cases) {
        readint(n); readint(d);
        vector<int> ans(n);
        map<int, vector<int>> vals;
        forr(i,0,n) {
            readint(aa);
            vals[aa].push_back(i);
        }

        block bl(n, d);
        int ret = 0;
        SegmentTree2<int> seg_tree(n, [](int x, int y){ return max(x,y); }, 0);

        auto it = vals.end();
        while (it!=vals.begin()) {
            --it;
            for(int j : it->second) {
                int val = 1 + seg_tree.GetEvaluation(j+1, bl.upto(j+1));
                bl.add(j);
                seg_tree.SetVal(j, val);
                ret = max(ret, val);
            }
        }

        cout << ret << endl;

    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'int block_correct::upto(int)':
Main.cpp:29:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
Main.cpp:129:11: note: in expansion of macro 'forr'
  129 |           forr(j,i,occupied.size()) {
      |           ^~~~
Main.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |               if (j+dd>occupied.size()) { break; }
      |                   ~~~~^~~~~~~~~~~~~~~~
Main.cpp: In constructor 'block::block(int, int)':
Main.cpp:149:11: warning: 'block::n' will be initialized after [-Wreorder]
  149 |       int n;
      |           ^
Main.cpp:148:11: warning:   'int block::d' [-Wreorder]
  148 |       int d;
      |           ^
Main.cpp:151:7: warning:   when initialized here [-Wreorder]
  151 |       block(int nn, int dd) : n(nn), d(dd) {}
      |       ^~~~~
Main.cpp: In instantiation of 'void SegmentTree2<T>::Initialize(const std::vector<_Tp>&) [with T = int]':
Main.cpp:56:11:   required from 'SegmentTree2<T>::SegmentTree2(int, std::function<T(T, T)>, T) [with T = int]'
Main.cpp:222:78:   required from here
Main.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |           while(B < data.size()) {B *= 2;  }
      |                 ~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35