oj.uz

Submission #674975

# Submission time Handle Problem Language Result Execution time Memory
674975 2022-12-26T18:11:06 Z Summers Trading (IZhO13_trading) C++17
100 / 100
 191 ms 19660 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 224 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 82 ms 9808 KB Output is correct
8 Correct 95 ms 11168 KB Output is correct
9 Correct 99 ms 11496 KB Output is correct
10 Correct 109 ms 12108 KB Output is correct
11 Correct 123 ms 13568 KB Output is correct
12 Correct 121 ms 13852 KB Output is correct
13 Correct 119 ms 14768 KB Output is correct
14 Correct 122 ms 14916 KB Output is correct
15 Correct 139 ms 16176 KB Output is correct
16 Correct 143 ms 16576 KB Output is correct
17 Correct 139 ms 16888 KB Output is correct
18 Correct 172 ms 17608 KB Output is correct
19 Correct 150 ms 17928 KB Output is correct
20 Correct 191 ms 19660 KB Output is correct