Submission #674975

#	Time	Username	Problem	Language	Result	Execution time	Memory
674975		Summers	Trading (IZhO13_trading)	C++17	100 / 100	191 ms	19660 KiB

trading

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long tree[1500000], ans[1000000];

void update(long long le,long long ri,long long l,long long r,long long ind,long long val)
{
    if(le>r || ri<l)return;

    if(l<=le && ri<=r)
    {
        tree[ind]=max(tree[ind], val);
        return;
    }
    long long mid=(le+ri)/2;

    update(le,mid,l,r,2*ind,val);
    update(mid+1,ri,l,r,2*ind+1,val);

}
void query(long long le,long long ri,long long ind)
{
    if(le==ri)
    {
        ans[le]=tree[ind];
        return;
    }
    long long mid=(le+ri)/2;

    tree[2*ind]=max(tree[2*ind],tree[ind]);
    tree[2*ind+1]=max(tree[2*ind+1],tree[ind]);

    query(le,mid,2*ind);
    query(mid+1,ri,2*ind+1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n,m,i,j,l,r,x;

    cin>>n>>m;

    for(i=0;i<=4*n;i++)tree[i]=-100000000000;

    for(i=1;i<=m;i++)
    {
        cin>>l>>r>>x;

        update(1,n,l,r,1,x-l);
    }
    query(1,n,1);

    for(i=1;i<=n;i++)cout<<max((long long)(0),ans[i]+i)<<" ";
    cout<<endl;

}

Compilation message (stderr)

trading.cpp: In function 'int main()':
trading.cpp:42:21: warning: unused variable 'j' [-Wunused-variable]
   42 |     long long n,m,i,j,l,r,x;
      |                     ^

• Subtask 1: 100 / 100