oj.uz

Submission #868541

# Submission time Handle Problem Language Result Execution time Memory
868541 2023-10-31T17:50:18 Z alexdd Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 59884 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
int tole[1000005];
int rez[1000005];
deque<int> dq;
vector<pair<pair<int,int>,int>> qrys[1000005];
int aib[10000005];
int qry(int poz)
{
    int aux=0;
    for(int i=poz;i<=n;i+=(i&(-i)))
        aux=max(aux,aib[i]);
    return aux;
}
void upd(int poz, int newv)
{
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[poz]=max(aib[poz],newv);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        while(!dq.empty() && a[dq.back()]<=a[i])
            dq.pop_back();
        if(dq.empty())
            tole[i]=0;
        else
            tole[i]=dq.back();
        dq.push_back(i);
    }
    int ql,qr,k;
    for(int i=1;i<=m;i++)
    {
        cin>>ql>>qr>>k;
        qrys[qr].push_back({{ql,k},i});
    }
    for(int i=1;i<=n;i++)
    {
        if(tole[i]>0) upd(tole[i],a[i]+tole[i]);
        for(auto x:qrys[i])
        {
            int le=x.first.first;
            ///int mxm=qry(le);
            int mxm=0;
            for(int j=1;j<=i;j++)
                if(tole[j]>=le)
                    mxm=max(mxm, a[j]+a[tole[j]]);
            if(mxm<=x.first.second)
                rez[x.second]=1;
            else
                rez[x.second]=0;
        }
    }
    for(int i=1;i<=m;i++)
        cout<<rez[i]<<"\n";
    return 0;
}
/**
tole[i] = prima pozitie din stanga lui i > a[i]
max(a[j] + a[tole[j]]) pt j = le..ri && tole[j] >= le

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31068 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 6 ms 31064 KB Output is correct
5 Correct 6 ms 31068 KB Output is correct
6 Correct 7 ms 31252 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 6 ms 31068 KB Output is correct
10 Correct 7 ms 31248 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31068 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 6 ms 31064 KB Output is correct
5 Correct 6 ms 31068 KB Output is correct
6 Correct 7 ms 31252 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 6 ms 31068 KB Output is correct
10 Correct 7 ms 31248 KB Output is correct
11 Correct 10 ms 31064 KB Output is correct
12 Correct 15 ms 31320 KB Output is correct
13 Correct 17 ms 31332 KB Output is correct
14 Correct 23 ms 31372 KB Output is correct
15 Correct 23 ms 31324 KB Output is correct
16 Correct 26 ms 31356 KB Output is correct
17 Correct 22 ms 31324 KB Output is correct
18 Correct 25 ms 31320 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 59884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 33856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31068 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 6 ms 31064 KB Output is correct
5 Correct 6 ms 31068 KB Output is correct
6 Correct 7 ms 31252 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 6 ms 31068 KB Output is correct
10 Correct 7 ms 31248 KB Output is correct
11 Correct 10 ms 31064 KB Output is correct
12 Correct 15 ms 31320 KB Output is correct
13 Correct 17 ms 31332 KB Output is correct
14 Correct 23 ms 31372 KB Output is correct
15 Correct 23 ms 31324 KB Output is correct
16 Correct 26 ms 31356 KB Output is correct
17 Correct 22 ms 31324 KB Output is correct
18 Correct 25 ms 31320 KB Output is correct
19 Execution timed out 3041 ms 36304 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31068 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 6 ms 31064 KB Output is correct
5 Correct 6 ms 31068 KB Output is correct
6 Correct 7 ms 31252 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 6 ms 31068 KB Output is correct
9 Correct 6 ms 31068 KB Output is correct
10 Correct 7 ms 31248 KB Output is correct
11 Correct 10 ms 31064 KB Output is correct
12 Correct 15 ms 31320 KB Output is correct
13 Correct 17 ms 31332 KB Output is correct
14 Correct 23 ms 31372 KB Output is correct
15 Correct 23 ms 31324 KB Output is correct
16 Correct 26 ms 31356 KB Output is correct
17 Correct 22 ms 31324 KB Output is correct
18 Correct 25 ms 31320 KB Output is correct
19 Execution timed out 3029 ms 59884 KB Time limit exceeded
20 Halted 0 ms 0 KB -