oj.uz

Submission #928240

# Submission time Handle Problem Language Result Execution time Memory
928240 2024-02-16T05:50:56 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 3000 ms 35232 KB 
#include <bits/stdc++.h>
#define S second
#define F first
#define sz size()
#define int long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define yes "YES\n"
#define no "NO\n"
#define ent "\n"
#define give_me_more_speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const int maxn = 1e6 + 5, mod = 1e9 + 7;

int pref[maxn];

int a[maxn] , t[maxn * 4];

void build(int v ,int tl , int tr){
  if(tl == tr){
    t[v] = a[tl];
    return;
  }
  int tm = tl + tr >> 1;
  build(v * 2, tl ,tm);
  build(v * 2 + 1 , tm + 1 , tr);
  t[v] = max(t[v * 2] , t[v * 2 + 1]);
}

int get(int v ,int tl , int tr , int l , int r){
  if(tl > r || l > tr) return 0;
  if(l <= tl && tr <= r) return t[v];
  int tm = tl + tr >> 1;
  return max(get(v * 2 , tl , tm , l , r) , get(v * 2 + 1, tm + 1 , tr , l , r));
}

void solve(){
  int n , q;
  cin >> n >> q;
  pref[1] = 0;
  for(int i = 1;i <= n;i++){
    cin >> a[i];
    if(i > 1){
      pref[i] = pref[i - 1] + (a[i - 1] <= a[i]);
    }
  }
  build(1 , 1 , n);
  int mn = *min_element(a + 1,a + 1 + n);
  // cout<<mn<<ent;
  while(q--){
    int l , r , k;
    cin >> l >> r >> k;
    if(k < mn){
      // cout<<pref[r] - pref[l]<<ent;
      if(pref[r] - pref[l] == (r - l)){
        cout<<1<<ent;
      }
      else cout<<0<<ent;
      continue;
    }
    int ok = 1;
    for(int i = l + 1;i <= r;i++){
      int mx = get(1 , 1 , n, l , i - 1);
      if(mx + a[i] > k && mx > a[i]){
        ok = 0;
        break;
      }
    }
    cout<<ok<<ent;
  }
}

signed main(){
  give_me_more_speed
  int t = 1;
  //cin>>t;
  for(int i = 1;i <= t;i++){
      solve();
  }
}

Compilation message

sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 8 ms 4444 KB Output is correct
9 Correct 4 ms 4444 KB Output is correct
10 Correct 6 ms 4444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 8 ms 4444 KB Output is correct
9 Correct 4 ms 4444 KB Output is correct
10 Correct 6 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 8 ms 6748 KB Output is correct
13 Correct 8 ms 6752 KB Output is correct
14 Correct 13 ms 6748 KB Output is correct
15 Correct 10 ms 6744 KB Output is correct
16 Correct 979 ms 6728 KB Output is correct
17 Correct 932 ms 6488 KB Output is correct
18 Correct 858 ms 6736 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 35044 KB Output is correct
2 Correct 404 ms 35052 KB Output is correct
3 Correct 356 ms 34956 KB Output is correct
4 Correct 381 ms 35232 KB Output is correct
5 Correct 375 ms 34900 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 8 ms 4444 KB Output is correct
9 Correct 4 ms 4444 KB Output is correct
10 Correct 6 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 8 ms 6748 KB Output is correct
13 Correct 8 ms 6752 KB Output is correct
14 Correct 13 ms 6748 KB Output is correct
15 Correct 10 ms 6744 KB Output is correct
16 Correct 979 ms 6728 KB Output is correct
17 Correct 932 ms 6488 KB Output is correct
18 Correct 858 ms 6736 KB Output is correct
19 Execution timed out 3031 ms 10876 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 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 8 ms 4444 KB Output is correct
9 Correct 4 ms 4444 KB Output is correct
10 Correct 6 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 8 ms 6748 KB Output is correct
13 Correct 8 ms 6752 KB Output is correct
14 Correct 13 ms 6748 KB Output is correct
15 Correct 10 ms 6744 KB Output is correct
16 Correct 979 ms 6728 KB Output is correct
17 Correct 932 ms 6488 KB Output is correct
18 Correct 858 ms 6736 KB Output is correct
19 Correct 385 ms 35044 KB Output is correct
20 Correct 404 ms 35052 KB Output is correct
21 Correct 356 ms 34956 KB Output is correct
22 Correct 381 ms 35232 KB Output is correct
23 Correct 375 ms 34900 KB Output is correct
24 Execution timed out 3061 ms 9044 KB Time limit exceeded
25 Halted 0 ms 0 KB -