Submission #530748

#	Time	Username	Problem	Language	Result	Execution time	Memory
530748		Mounir	Financial Report (JOI21_financial)	C++14	100 / 100	559 ms	49384 KiB

Main

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define x first
#define y second
#define int long long
using namespace std;

const int N = (1 << 19);
int tree[N * 2][2];

int comb(int a, int b, int op){
      if (op == 0)
            return max(a, b);
      return min(a, b);
}

void upd(int ind, int op, int val, bool force){
      if (!force)
            tree[ind][op] = comb(tree[ind][op], val, op);
      else
            tree[ind][op] = val;
      ind /= 2;
      for (; ind > 0; ind /= 2)
            tree[ind][op] = comb(tree[ind * 2][op], tree[ind * 2 + 1][op], op);
}

int getRes(int op, int inf, int sup){
      if (inf > sup) return 0;
      int res = tree[inf][op];
      while (sup >= inf){
            if (inf%2 == 1)
                  res = comb(res, tree[inf++][op], op);
            if (sup%2 == 0)
                  res = comb(res, tree[sup--][op], op);
            sup /= 2;
            inf /= 2;
      }
      return res;
}

signed main(){
      int nVals, d; cin >> nVals >> d; 
      vector<int> vals(nVals), tri;
      for (int& val : vals){
            cin >> val;
            tri.pb(val);
      }
      sort(all(tri));
      map<int, int> conv;
      for (int i = 0; i < nVals; ++i)
            conv[tri[i]] = i;
      for (int& val : vals)
            val = conv[val];
      
      //Re-indexage
      for (int i = 0; i < N * 2; ++i)
            tree[i][1] = nVals;
      priority_queue<int, vector<int>, greater<int>> presentes; //les vals presentes
      upd(N, 1, vals[0], true);
      upd(N + vals[0], 0, 1, true);
      presentes.push(vals[0]);
      for (int i = 1; i < nVals; ++i){
            //Gerter tous ceux trop loin
       //     cout << "ID " << i << endl;
            if (i > d){
                  int borneInf = getRes(1, N + i - d, N + i - 1);
                //  cout << "borne " << borneInf << endl;
                  while (!presentes.empty() && presentes.top() < borneInf){
                   //     cout << "tej" << presentes.top() << endl;
                        upd(N + presentes.top(), 0, 0, true);
                        presentes.pop();
                  }
            }
            upd(N + i, 1, vals[i], true);
            int resCur = getRes(0, N, N + vals[i] - 1) + 1;
        //    cout << "res " << vals[i] << " : " << resCur << endl;
            upd(N + vals[i], 0, resCur, false);
            presentes.push(vals[i]);
      }

      cout << tree[1][0] << endl;
      return 0;   
}

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