oj.uz

Submission #499736

# Submission time Handle Problem Language Result Execution time Memory
499736 2021-12-29T11:29:25 Z SOIVIEONE Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 6832 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 322222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const ll MOD = 1000000007ll;

ll bn(ll aa, ll n)
{
    ll r = 1ll;
    for(; n > 0; n >>= 1ll)
    {
        if(n & 1)
            r = (r * aa) % MOD;
        aa = (aa * aa) % MOD;
    }
    return r;

}

const ld pi = 2 * acos(0.0);
//template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

/*

 m/2 + 1

 5 5
1 +++--
2 +++--
3 +++--
4 +++--
5 +++--

12

1 -++--++
2 --++-++
3 ---++++
4 ---++++
5 +---+++
6 ++---++
7 +++--++

1 -++-++
2 --++++
3 --++++
4 --++++
5 +--+++
6 ++--++
 m - (m/2+1)
 m/2 + 1

 n/2+1
n

 n >= m
 m > n
 swap(n, m)
 heruistics

10 20
--+-+-++++
--+-+-++++
-+--+-++++
-+--+-++++
-+-+--++++
-+-+--++++
+--+-+-+++
+--+-+-+++
+-+--+-+++
+-+--+-+++

10 10
--+-+-++++
--+-+-++++
-+--+-++++
-+--+-++++
-+-+--++++
-+-+--++++
+--+-+-+++
+--+-+-+++
+-+--+-+++
+-+--+-+++



 8 1 7 3 4 5 6 10
 0 1 1 2 2 2 2  0

++++---
++++---
++++---
-------
---++++
---++++
---++++

-
-
-
-
+
+
+

*/
ll a[N];
void solve()
{
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    for(int i = 1; i <= m; i ++)
    {
        ll l, r, k;
        cin >> l >> r >> k;

        ll leftMax = 0, ans = 0;
        for(int j = l; j <= r; j ++)
        {
            if(leftMax > a[j])
                ans = max(ans, leftMax + a[j]);
            leftMax = max(leftMax, a[j]);
        }
        cout << (ans <= k) << '\n';
    }
}


int main()
{
    int t = 1;
    while(t --)
        solve();
    return 0;

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 9 ms 372 KB Output is correct
12 Correct 12 ms 416 KB Output is correct
13 Correct 14 ms 452 KB Output is correct
14 Correct 21 ms 492 KB Output is correct
15 Correct 23 ms 544 KB Output is correct
16 Correct 27 ms 332 KB Output is correct
17 Correct 27 ms 460 KB Output is correct
18 Correct 27 ms 428 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 118 ms 6832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2741 ms 3360 KB Output is correct
2 Execution timed out 3073 ms 2272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 9 ms 372 KB Output is correct
12 Correct 12 ms 416 KB Output is correct
13 Correct 14 ms 452 KB Output is correct
14 Correct 21 ms 492 KB Output is correct
15 Correct 23 ms 544 KB Output is correct
16 Correct 27 ms 332 KB Output is correct
17 Correct 27 ms 460 KB Output is correct
18 Correct 27 ms 428 KB Output is correct
19 Execution timed out 3050 ms 5292 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 9 ms 372 KB Output is correct
12 Correct 12 ms 416 KB Output is correct
13 Correct 14 ms 452 KB Output is correct
14 Correct 21 ms 492 KB Output is correct
15 Correct 23 ms 544 KB Output is correct
16 Correct 27 ms 332 KB Output is correct
17 Correct 27 ms 460 KB Output is correct
18 Correct 27 ms 428 KB Output is correct
19 Runtime error 118 ms 6832 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -