oj.uz

Submission #928468

# Submission time Handle Problem Language Result Execution time Memory
928468 2024-02-16T12:54:04 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1366 ms 142012 KB 
// Problem: A - Hedgehog Daniyar and Algorithms
// Contest: Virtual Judge - IOI contest #3 (div 1 + 2)
// URL: https://vjudge.net/contest/610287#problem/A
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#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;

vector <int> g[maxn];

int ans[maxn];
deque <int> dq;
int a[maxn] , t[maxn * 4];

void upd(int v ,int tl , int tr , int pos , int val){
  if(pos < tl || tr < pos) return;
  if(tl == tr){
    t[v] = max(val + a[pos], t[v]);
    return;
  }
  int tm = tl + tr >> 1;
  upd(v * 2 , tl , tm , pos , val);
  upd(v * 2 + 1 ,tm + 1 , tr , pos , val);
  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 , m;
  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()){
      ans[i] = -1;
    } 
    else ans[i] = dq.back();
    dq.pb(i);
  }
  int res[m + 5];
  int l[m + 5] , r[m + 5] , k[m + 5];
  for(int i = 1;i <= m;i++){
    cin>>l[i] >> r[i] >> k[i];
    g[r[i]].pb(i);
  }
  for(int i = 1;i <= n;i++){
    if(ans[i] != -1) upd(1 , 1 , n , ans[i] , a[i]);
    for(auto to : g[i]){
      res[to] = get(1 , 1 , n , l[to] , r[to]) > k[to] ? 0 : 1;
    }
  }
  for(int i = 1;i <= m;i++){
    cout<<res[i]<<ent;
  }
}

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

Compilation message

sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   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:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29528 KB Output is correct
2 Correct 6 ms 29528 KB Output is correct
3 Correct 6 ms 29532 KB Output is correct
4 Correct 6 ms 29640 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 9 ms 29684 KB Output is correct
7 Correct 6 ms 29532 KB Output is correct
8 Correct 6 ms 29528 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29784 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29528 KB Output is correct
2 Correct 6 ms 29528 KB Output is correct
3 Correct 6 ms 29532 KB Output is correct
4 Correct 6 ms 29640 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 9 ms 29684 KB Output is correct
7 Correct 6 ms 29532 KB Output is correct
8 Correct 6 ms 29528 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29784 KB Output is correct
11 Correct 10 ms 29892 KB Output is correct
12 Correct 9 ms 32072 KB Output is correct
13 Correct 9 ms 32092 KB Output is correct
14 Correct 12 ms 32108 KB Output is correct
15 Correct 10 ms 32092 KB Output is correct
16 Correct 11 ms 31940 KB Output is correct
17 Correct 12 ms 32088 KB Output is correct
18 Correct 9 ms 32092 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 109868 KB Output is correct
2 Correct 1347 ms 134528 KB Output is correct
3 Correct 1350 ms 134328 KB Output is correct
4 Correct 1364 ms 134704 KB Output is correct
5 Correct 1044 ms 118236 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 38736 KB Output is correct
2 Correct 77 ms 40272 KB Output is correct
3 Correct 67 ms 38548 KB Output is correct
4 Correct 68 ms 38676 KB Output is correct
5 Correct 70 ms 38696 KB Output is correct
6 Correct 56 ms 37968 KB Output is correct
7 Correct 59 ms 37968 KB Output is correct
8 Correct 65 ms 38356 KB Output is correct
9 Correct 36 ms 35292 KB Output is correct
10 Correct 65 ms 38344 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29528 KB Output is correct
2 Correct 6 ms 29528 KB Output is correct
3 Correct 6 ms 29532 KB Output is correct
4 Correct 6 ms 29640 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 9 ms 29684 KB Output is correct
7 Correct 6 ms 29532 KB Output is correct
8 Correct 6 ms 29528 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29784 KB Output is correct
11 Correct 10 ms 29892 KB Output is correct
12 Correct 9 ms 32072 KB Output is correct
13 Correct 9 ms 32092 KB Output is correct
14 Correct 12 ms 32108 KB Output is correct
15 Correct 10 ms 32092 KB Output is correct
16 Correct 11 ms 31940 KB Output is correct
17 Correct 12 ms 32088 KB Output is correct
18 Correct 9 ms 32092 KB Output is correct
19 Correct 208 ms 52564 KB Output is correct
20 Correct 195 ms 52816 KB Output is correct
21 Correct 167 ms 51508 KB Output is correct
22 Correct 176 ms 51544 KB Output is correct
23 Correct 182 ms 51428 KB Output is correct
24 Correct 133 ms 47116 KB Output is correct
25 Correct 138 ms 47184 KB Output is correct
26 Correct 142 ms 47772 KB Output is correct
27 Correct 145 ms 47696 KB Output is correct
28 Correct 151 ms 47952 KB Output is correct
29 Correct 154 ms 48720 KB Output is correct
30 Correct 157 ms 48580 KB Output is correct
31 Correct 152 ms 48464 KB Output is correct
32 Correct 156 ms 48468 KB Output is correct
33 Correct 156 ms 48464 KB Output is correct
34 Correct 122 ms 46676 KB Output is correct
35 Correct 121 ms 46672 KB Output is correct
36 Correct 118 ms 46496 KB Output is correct
37 Correct 124 ms 46536 KB Output is correct
38 Correct 134 ms 46852 KB Output is correct
39 Correct 142 ms 48256 KB Output is correct
40 Correct 112 ms 45760 KB Output is correct
41 Correct 140 ms 46648 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 29528 KB Output is correct
2 Correct 6 ms 29528 KB Output is correct
3 Correct 6 ms 29532 KB Output is correct
4 Correct 6 ms 29640 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 9 ms 29684 KB Output is correct
7 Correct 6 ms 29532 KB Output is correct
8 Correct 6 ms 29528 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29784 KB Output is correct
11 Correct 10 ms 29892 KB Output is correct
12 Correct 9 ms 32072 KB Output is correct
13 Correct 9 ms 32092 KB Output is correct
14 Correct 12 ms 32108 KB Output is correct
15 Correct 10 ms 32092 KB Output is correct
16 Correct 11 ms 31940 KB Output is correct
17 Correct 12 ms 32088 KB Output is correct
18 Correct 9 ms 32092 KB Output is correct
19 Correct 1366 ms 109868 KB Output is correct
20 Correct 1347 ms 134528 KB Output is correct
21 Correct 1350 ms 134328 KB Output is correct
22 Correct 1364 ms 134704 KB Output is correct
23 Correct 1044 ms 118236 KB Output is correct
24 Correct 88 ms 38736 KB Output is correct
25 Correct 77 ms 40272 KB Output is correct
26 Correct 67 ms 38548 KB Output is correct
27 Correct 68 ms 38676 KB Output is correct
28 Correct 70 ms 38696 KB Output is correct
29 Correct 56 ms 37968 KB Output is correct
30 Correct 59 ms 37968 KB Output is correct
31 Correct 65 ms 38356 KB Output is correct
32 Correct 36 ms 35292 KB Output is correct
33 Correct 65 ms 38344 KB Output is correct
34 Correct 208 ms 52564 KB Output is correct
35 Correct 195 ms 52816 KB Output is correct
36 Correct 167 ms 51508 KB Output is correct
37 Correct 176 ms 51544 KB Output is correct
38 Correct 182 ms 51428 KB Output is correct
39 Correct 133 ms 47116 KB Output is correct
40 Correct 138 ms 47184 KB Output is correct
41 Correct 142 ms 47772 KB Output is correct
42 Correct 145 ms 47696 KB Output is correct
43 Correct 151 ms 47952 KB Output is correct
44 Correct 154 ms 48720 KB Output is correct
45 Correct 157 ms 48580 KB Output is correct
46 Correct 152 ms 48464 KB Output is correct
47 Correct 156 ms 48468 KB Output is correct
48 Correct 156 ms 48464 KB Output is correct
49 Correct 122 ms 46676 KB Output is correct
50 Correct 121 ms 46672 KB Output is correct
51 Correct 118 ms 46496 KB Output is correct
52 Correct 124 ms 46536 KB Output is correct
53 Correct 134 ms 46852 KB Output is correct
54 Correct 142 ms 48256 KB Output is correct
55 Correct 112 ms 45760 KB Output is correct
56 Correct 140 ms 46648 KB Output is correct
57 Correct 1329 ms 141876 KB Output is correct
58 Correct 1350 ms 142012 KB Output is correct
59 Correct 1211 ms 139116 KB Output is correct
60 Correct 1267 ms 139000 KB Output is correct
61 Correct 1185 ms 139092 KB Output is correct
62 Correct 1232 ms 139016 KB Output is correct
63 Correct 743 ms 117584 KB Output is correct
64 Correct 754 ms 117612 KB Output is correct
65 Correct 942 ms 122340 KB Output is correct
66 Correct 983 ms 122280 KB Output is correct
67 Correct 990 ms 122608 KB Output is correct
68 Correct 1025 ms 125440 KB Output is correct
69 Correct 1034 ms 125436 KB Output is correct
70 Correct 1049 ms 125008 KB Output is correct
71 Correct 1014 ms 124908 KB Output is correct
72 Correct 1025 ms 124856 KB Output is correct
73 Correct 744 ms 118052 KB Output is correct
74 Correct 715 ms 119324 KB Output is correct
75 Correct 724 ms 118112 KB Output is correct
76 Correct 710 ms 118080 KB Output is correct
77 Correct 719 ms 118100 KB Output is correct
78 Correct 943 ms 123480 KB Output is correct
79 Correct 658 ms 108460 KB Output is correct
80 Correct 943 ms 116108 KB Output is correct