Submission #1244313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244313		emad234	Financial Report (JOI21_financial)	C++20	0 / 100	118 ms	6480 KiB

Main

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = 2e6 + 5;
const int mod = 1e9 + 7;
using namespace std;
int dp[mxN];
pii a[mxN];
int n,d;
set<pii>s;
int seg[mxN];
int N;
int query(int l,int r,int ind,int s,int e){
  if(l > e || r < s) return 0;
  if(l >= s && r <= e) return seg[ind];
  int md = (l + r) / 2;
  return max(query(l,md,ind * 2,s,e),query(md + 1,r,ind * 2 + 1,s,e));
}
void update(int ind,int val){
  ind += N;
  seg[ind] = val;
  ind /= 2;
  for(ind;ind;ind /= 2) seg[ind] = max(seg[ind * 2],seg[ind * 2 + 1]);
}
signed main(){
  int ans = 0;
  cin >>n;
  d = n;
  N = exp2(ceil(log2(n)));
  for(int i = 1;i <= n;i++) {
    cin >>a[i].F;
    a[i].S = i;
  }
  sort(a + 1,a + n + 1);
  s.insert({1,n});
  int prev = -1;
  queue<pii>buff;
  for(int i = 1;i <= n;i++){
    if(a[i].F != prev){
      prev = a[i].F;
      while(buff.size()){
        auto u = buff.front();
        buff.pop();
        update(u.F,u.S);
      }
    }
    int l = 1,r = a[i].S - 1;
    if(s.size()){
      auto x = s.upper_bound({a[i].S,1e9});
      if(x != s.begin()){
        x--;
        if(x->F <= a[i].S && x->S >= a[i].S){
          pii y = {x->F,a[i].S - 1},z = {a[i].S + 1,x->S};
          s.erase(x);
          if(y.S - y.F + 1 >= d) s.insert(y);
          if(z.S - z.F + 1 >= d) s.insert(z);
        }
      }
      if(s.size()){
        x = s.upper_bound({a[i].S,0});
        if(x != s.begin()){
          x--;
          l = x->S + 1;
        }
      }
    }
    dp[a[i].S] = query(1,N,1,l,r) + 1;
    // cout<<l<<' '<<r<<'\n';
    // cout<<a[i].F<<' '<<a[i].S<<' '<<dp[a[i].S]<<'\n';
    ans = max(ans,dp[a[i].S]);
    buff.push({a[i].S - 1,dp[a[i].S]});
  }
  cout<<ans;
}

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