oj.uz

Submission #494113

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

using namespace std;
int n,m,v[1000005],st[1000005],dr[1000005],cost[1000005];
vector <int> ev[1000005];
int aib[1000005],i,j,sol[1000005];
stack <int> stac;
int ub (int x)
{
    return x&(-x);
}
void update(int poz,int x)
{
    for (int i=poz;i<=n;i+=ub(i))
    {
        aib[i]=max(aib[i],x);
    }
}
int maxi(int poz)
{
    int maxim=0;
    for (int i=poz;i>=1;i-=ub(i))
    {
        maxim=max(aib[i],maxim);
    }
    return maxim;
}
vector <pair <int,int>> ceau;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    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 12 ms 23756 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Incorrect 12 ms 23756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Incorrect 12 ms 23756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Incorrect 12 ms 23756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23756 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Incorrect 12 ms 23756 KB Output isn't correct
4 Halted 0 ms 0 KB -