oj.uz

Submission #911214

# Submission time Handle Problem Language Result Execution time Memory
911214 2024-01-18T15:51:29 Z cadmiumsky Fish 2 (JOI22_fish2) C++17
5 / 100
 4000 ms 2908 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

int check(vector<int>& v, int p, int l, int r) {
  priority_queue<pii, vector<pii>, greater<pii>> heap;
  heap.emplace(v[p - 1], p - 1);
  heap.emplace(v[p + 1], p + 1);
  
  int S = v[p];
  
  while(!heap.empty()) {
    auto [C, poz] = heap.top();
    heap.pop();
    if(poz > r || poz < l) continue;
    
    if(S < C) return 0;
    //cerr << S << ' ' << C << '\t' << p << ' ' << poz << '\n';
    S += C;
    if(p < poz) heap.emplace(v[poz + 1], poz + 1);
    if(p > poz) heap.emplace(v[poz - 1], poz - 1);
  }
  
  return 1;
  
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, q;
  cin >> n;
  
  vector<int> v(n + 1);
  for(int i = 1; i <= n; i++) cin >> v[i];
  
  cin >> q;
  
  v.emplace_back(0);
  
  for(int TC = 0, t, x, y; TC < q; TC++) {
    cin >> t >> x >> y;
    if(t == 1)
      v[x] = y;
    else {
      int cnt = 0;
      for(int i = x; i <= y; i++)
        cnt += check(v, i, x, y);
      cout << cnt << '\n';
    }
  }
  
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 348 KB Output is correct
6 Correct 16 ms 348 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 9 ms 348 KB Output is correct
9 Correct 41 ms 344 KB Output is correct
10 Correct 28 ms 348 KB Output is correct
11 Correct 73 ms 348 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 18 ms 476 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 13 ms 472 KB Output is correct
16 Correct 51 ms 348 KB Output is correct
17 Correct 8 ms 476 KB Output is correct
18 Correct 20 ms 348 KB Output is correct
19 Correct 20 ms 600 KB Output is correct
20 Correct 266 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3589 ms 1884 KB Output is correct
3 Correct 328 ms 2136 KB Output is correct
4 Correct 3370 ms 2396 KB Output is correct
5 Correct 385 ms 2140 KB Output is correct
6 Execution timed out 4041 ms 2908 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 348 KB Output is correct
6 Correct 16 ms 348 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 9 ms 348 KB Output is correct
9 Correct 41 ms 344 KB Output is correct
10 Correct 28 ms 348 KB Output is correct
11 Correct 73 ms 348 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 18 ms 476 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 13 ms 472 KB Output is correct
16 Correct 51 ms 348 KB Output is correct
17 Correct 8 ms 476 KB Output is correct
18 Correct 20 ms 348 KB Output is correct
19 Correct 20 ms 600 KB Output is correct
20 Correct 266 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 3589 ms 1884 KB Output is correct
23 Correct 328 ms 2136 KB Output is correct
24 Correct 3370 ms 2396 KB Output is correct
25 Correct 385 ms 2140 KB Output is correct
26 Execution timed out 4041 ms 2908 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3589 ms 1884 KB Output is correct
3 Correct 328 ms 2136 KB Output is correct
4 Correct 3370 ms 2396 KB Output is correct
5 Correct 385 ms 2140 KB Output is correct
6 Execution timed out 4041 ms 2908 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 3589 ms 1884 KB Output is correct
3 Correct 328 ms 2136 KB Output is correct
4 Correct 3370 ms 2396 KB Output is correct
5 Correct 385 ms 2140 KB Output is correct
6 Execution timed out 4041 ms 2908 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 348 KB Output is correct
6 Correct 16 ms 348 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 9 ms 348 KB Output is correct
9 Correct 41 ms 344 KB Output is correct
10 Correct 28 ms 348 KB Output is correct
11 Correct 73 ms 348 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 18 ms 476 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 13 ms 472 KB Output is correct
16 Correct 51 ms 348 KB Output is correct
17 Correct 8 ms 476 KB Output is correct
18 Correct 20 ms 348 KB Output is correct
19 Correct 20 ms 600 KB Output is correct
20 Correct 266 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 3589 ms 1884 KB Output is correct
23 Correct 328 ms 2136 KB Output is correct
24 Correct 3370 ms 2396 KB Output is correct
25 Correct 385 ms 2140 KB Output is correct
26 Execution timed out 4041 ms 2908 KB Time limit exceeded
27 Halted 0 ms 0 KB -