oj.uz

Submission #494117

# Submission time Handle Problem Language Result Execution time Memory
494117 2021-12-14T11:52:52 Z stefantaga Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 1827 ms 98872 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m,v[2000005],st[2000005],dr[2000005],cost[2000005];
vector <int> ev[2000005];
int aib[2000005],sol[2000005];
stack <int> stac;
int ub (int x)
{
    return x&(-x);
}
void update(int poz2,int x)
{
    int i;
    for (i=poz2;i<=n;i+=ub(i))
    {
        aib[i]=max(aib[i],x);
    }
}
int maxi(int poz2)
{
    int i,maxim=0;
    for (i=poz2;i>=1;i-=ub(i))
    {
        maxim=max(aib[i],maxim);
    }
    return maxim;
}
int i,j;
vector <pair <int,int>> ceau;
int main()
{
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for (i=1;i<=m;i++)
    {
        cin>>st[i]>>dr[i]>>cost[i];
        ev[st[i]].push_back(i);
    }
    for (i=1;i<=n;i++)
    {
        while (!stac.empty()&&v[stac.top()]<=v[i])
        {
            stac.pop();
        }
        if (!stac.empty())
        {
            ceau.push_back({stac.top(),i});
        }
        stac.push(i);
    }
    int poz=((int)ceau.size())-1;
    for (i=n;i>=1;i--)
    {
        while (poz>=0&&ceau[poz].first>=i)
        {
            update(ceau[poz].second,v[ceau[poz].first]+v[ceau[poz].second]);
            poz--;
        }
        for (j=0;j<(int)ev[i].size();j++)
        {
            if (maxi(dr[ev[i][j]])<=cost[ev[i][j]])
            {
                sol[ev[i][j]]=1;
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        cout<<sol[i]<<'\n';
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47308 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Incorrect 22 ms 47272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47308 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Incorrect 22 ms 47272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1827 ms 98872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 52664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47308 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Incorrect 22 ms 47272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47308 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Incorrect 22 ms 47272 KB Output isn't correct
4 Halted 0 ms 0 KB -