Submission #420286

#	Time	Username	Problem	Language	Result	Execution time	Memory
420286		Sho10	Financial Report (JOI21_financial)	C++17	100 / 100	743 ms	48536 KiB

Main

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,d,a[300005],tree[3][1200005],lazy[12000005];
map<ll,ll>m;
void build(ll node,ll l,ll r){
if(l==r){
    tree[1][node]=a[l];
    return;
}
ll mid=(l+r)/2;
build(2*node,l,mid);
build(2*node+1,mid+1,r);
tree[1][node]=min(tree[1][2*node],tree[1][2*node+1]);
}
ll query1(ll node,ll l,ll r,ll st,ll dr){
if(l>dr){
    return LINF;
}
if(r<st){
    return LINF;
}
if(st<=l&&r<=dr){
    return tree[1][node];
}
ll mid=(l+r)/2;
return min(query1(2*node,l,mid,st,dr),query1(2*node+1,mid+1,r,st,dr));
}
void push(ll node,ll l,ll r){
if(lazy[node]==1){
    tree[2][node]=0;
    if(l!=r){
        lazy[2*node]=1;
        lazy[2*node+1]=1;
    }
    lazy[node]=0;
}
}
void update2(ll node,ll l,ll r,ll st,ll dr){
push(node,l,r);
if(l>dr){
    return;
}
if(r<st){
    return;
}
if(st<=l&&r<=dr){
    lazy[node]=1;
    push(node,l,r);
    return;
}
ll mid=(l+r)/2;
update2(2*node,l,mid,st,dr);
update2(2*node+1,mid+1,r,st,dr);
tree[2][node]=max(tree[2][node*2],tree[2][node*2+1]);
}
ll query2(ll node,ll l,ll r,ll st,ll dr){
push(node,l,r);
if(l>dr){
    return 0;
}
if(r<st){
    return 0;
}
if(st<=l&&r<=dr){
    return tree[2][node];
}
ll mid=(l+r)/2;
return max(query2(2*node,l,mid,st,dr),query2(2*node+1,mid+1,r,st,dr));
}
void update3(ll node,ll l,ll r,ll pos,ll val){
push(node,l,r);
if(l==r){
    tree[2][node]=max(tree[2][node],val);
    return;
}
ll mid=(l+r)/2;
tree[2][node]=max(tree[2][node],val);
if(pos<=mid){
    update3(2*node,l,mid,pos,val);
}else {
update3(2*node+1,mid+1,r,pos,val);
}
}
int32_t main(){
CODE_START;
cin>>n>>d;
vector<ll>v;
for(ll i=1;i<=n;i++)
{
    cin>>a[i];
    v.pb(a[i]);
}
sort(v.begin(),v.end());
ll s1=0;
for(ll i=0;i<v.size();i++)
{
    if(i==0||v[i]!=v[i-1]){
        m[v[i]]=++s1;
    }
}
for(ll i=1;i<=n;i++)
{
    a[i]=m[a[i]];
}
build(1,1,n);
for(ll i=1;i<=n;i++)
{
    if(i>=2){
        ll nr=query1(1,1,n,max(1ll,i-d),i-1);
        if(nr>=2){
            update2(1,1,n,1,nr-1);
        }
}
ll val=1;
if(a[i]>=2){
    val+=query2(1,1,n,1,a[i]-1);
}
update3(1,1,n,a[i],val);
}
cout<<tree[2][1]<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:112:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 | for(ll i=0;i<v.size();i++)
      |            ~^~~~~~~~~

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