oj.uz

Submission #730163

# Submission time Handle Problem Language Result Execution time Memory
730163 2023-04-25T11:14:30 Z Sam_a17 Fish 2 (JOI22_fish2) C++17
25 / 100
 4000 ms 12456 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5 + 10, M = 2e5 + 10;
int a[N], n, q, ok[N], b[N];
long long p[N];

vector<int> indices[M];

void solve_() {
  cin >> n;

  vector<int> vals;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    vals.push_back(a[i]);
    p[i] = p[i - 1] + a[i];
  }

  vector<pair<int, pair<int, int>>> queries;

  int q; cin >> q;
  for(int i = 0; i < q; i++) {
    int t, l, r; cin >> t >> l >> r;
    if(t == 1) {
      vals.push_back(r);
    }
    queries.push_back({t, {l, r}});
  }

  sort(all(vals));
  uniq(vals);

  for(int i = 1; i <= n; i++) {
    b[i] = lower_bound(all(vals), a[i]) - vals.begin();
  }
 
  for(int i = 0; i < q; i++) {
    int type = queries[i].first;
 
    if(type == 1) {
      int x, y; 
      x = queries[i].second.first;
      y = queries[i].second.second;
      a[x] = y;
      b[x] = lower_bound(all(vals), y) - vals.begin();

      for(int i = 1; i <= n; i++) {
        p[i] = p[i - 1] + a[i];
      }
    } else {
      int l = queries[i].second.first;
      int r = queries[i].second.second;

      vector<int> lower_bigger(n + 1, l - 1);
      vector<int> upper_bigger(n + 1, r + 1);
  
      stack<pair<int, int>> st;
      for(int i = l; i <= r; i++) {
        while(!st.empty() && st.top().first < a[i]) {
          upper_bigger[st.top().second] = i;
          st.pop();
        }
        st.push({a[i], i});
        ok[i] = false;
        indices[b[i]].push_back(i);
      }

      while(!st.empty()) st.pop();

      for(int i = r; i >= l; i--) {
        while(!st.empty() && st.top().first < a[i]) {
          lower_bigger[st.top().second] = i;
          st.pop();
        }
        st.push({a[i], i});
      }

      int it = 0, answ = 0;
      for(int i = sz(vals) - 1; i >= 0; i--) {
        if(indices[i].empty()) continue;
        if(it == 0) {
          for(auto j: indices[i]) {
            ok[j] = true;
            answ++;
          }
        } else {
          for(auto j: indices[i]) {
            int li = lower_bigger[j], ri = upper_bigger[j];

            long long s = p[ri - 1] - p[li];
            if(li >= l && s >= a[li] && ok[li]) {
              ok[j] = true;
              answ++;
            } else if(ri <= r && s >= a[ri] && ok[ri]) {
              ok[j] = true;
              answ++;
            }
          }
        }

        indices[i].clear();
        it++;
      }
 
      cout << answ << '\n';
    }
  }
 
 
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

fish2.cpp: In function 'void setIO(std::string)':
fish2.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 6 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 7 ms 5076 KB Output is correct
10 Correct 6 ms 5076 KB Output is correct
11 Correct 8 ms 5040 KB Output is correct
12 Correct 5 ms 5036 KB Output is correct
13 Correct 8 ms 5076 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 5 ms 5076 KB Output is correct
16 Correct 6 ms 5076 KB Output is correct
17 Correct 5 ms 5076 KB Output is correct
18 Correct 7 ms 5032 KB Output is correct
19 Correct 6 ms 5092 KB Output is correct
20 Correct 11 ms 5076 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 30 ms 9772 KB Output is correct
3 Correct 21 ms 9100 KB Output is correct
4 Correct 30 ms 9772 KB Output is correct
5 Correct 21 ms 9044 KB Output is correct
6 Correct 48 ms 12184 KB Output is correct
7 Correct 19 ms 8900 KB Output is correct
8 Correct 48 ms 12204 KB Output is correct
9 Correct 19 ms 9008 KB Output is correct
10 Correct 29 ms 9548 KB Output is correct
11 Correct 19 ms 9004 KB Output is correct
12 Correct 21 ms 9044 KB Output is correct
13 Correct 21 ms 9016 KB Output is correct
14 Correct 22 ms 9464 KB Output is correct
15 Correct 23 ms 9452 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 6 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 7 ms 5076 KB Output is correct
10 Correct 6 ms 5076 KB Output is correct
11 Correct 8 ms 5040 KB Output is correct
12 Correct 5 ms 5036 KB Output is correct
13 Correct 8 ms 5076 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 5 ms 5076 KB Output is correct
16 Correct 6 ms 5076 KB Output is correct
17 Correct 5 ms 5076 KB Output is correct
18 Correct 7 ms 5032 KB Output is correct
19 Correct 6 ms 5092 KB Output is correct
20 Correct 11 ms 5076 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 30 ms 9772 KB Output is correct
23 Correct 21 ms 9100 KB Output is correct
24 Correct 30 ms 9772 KB Output is correct
25 Correct 21 ms 9044 KB Output is correct
26 Correct 48 ms 12184 KB Output is correct
27 Correct 19 ms 8900 KB Output is correct
28 Correct 48 ms 12204 KB Output is correct
29 Correct 19 ms 9008 KB Output is correct
30 Correct 29 ms 9548 KB Output is correct
31 Correct 19 ms 9004 KB Output is correct
32 Correct 21 ms 9044 KB Output is correct
33 Correct 21 ms 9016 KB Output is correct
34 Correct 22 ms 9464 KB Output is correct
35 Correct 23 ms 9452 KB Output is correct
36 Correct 768 ms 9300 KB Output is correct
37 Correct 1030 ms 9056 KB Output is correct
38 Correct 1107 ms 9148 KB Output is correct
39 Correct 460 ms 9256 KB Output is correct
40 Correct 1211 ms 9132 KB Output is correct
41 Correct 2176 ms 12184 KB Output is correct
42 Correct 2628 ms 12312 KB Output is correct
43 Correct 1266 ms 9040 KB Output is correct
44 Correct 1433 ms 8964 KB Output is correct
45 Correct 764 ms 9432 KB Output is correct
46 Correct 1077 ms 9664 KB Output is correct
47 Correct 1235 ms 9136 KB Output is correct
48 Correct 625 ms 8980 KB Output is correct
49 Correct 1464 ms 9088 KB Output is correct
50 Correct 882 ms 9452 KB Output is correct
51 Correct 3152 ms 9796 KB Output is correct
52 Correct 3708 ms 9828 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 30 ms 9772 KB Output is correct
3 Correct 21 ms 9100 KB Output is correct
4 Correct 30 ms 9772 KB Output is correct
5 Correct 21 ms 9044 KB Output is correct
6 Correct 48 ms 12184 KB Output is correct
7 Correct 19 ms 8900 KB Output is correct
8 Correct 48 ms 12204 KB Output is correct
9 Correct 19 ms 9008 KB Output is correct
10 Correct 29 ms 9548 KB Output is correct
11 Correct 19 ms 9004 KB Output is correct
12 Correct 21 ms 9044 KB Output is correct
13 Correct 21 ms 9016 KB Output is correct
14 Correct 22 ms 9464 KB Output is correct
15 Correct 23 ms 9452 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 4054 ms 11616 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 30 ms 9772 KB Output is correct
3 Correct 21 ms 9100 KB Output is correct
4 Correct 30 ms 9772 KB Output is correct
5 Correct 21 ms 9044 KB Output is correct
6 Correct 48 ms 12184 KB Output is correct
7 Correct 19 ms 8900 KB Output is correct
8 Correct 48 ms 12204 KB Output is correct
9 Correct 19 ms 9008 KB Output is correct
10 Correct 29 ms 9548 KB Output is correct
11 Correct 19 ms 9004 KB Output is correct
12 Correct 21 ms 9044 KB Output is correct
13 Correct 21 ms 9016 KB Output is correct
14 Correct 22 ms 9464 KB Output is correct
15 Correct 23 ms 9452 KB Output is correct
16 Correct 3 ms 5036 KB Output is correct
17 Execution timed out 4051 ms 12456 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 6 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 7 ms 5076 KB Output is correct
10 Correct 6 ms 5076 KB Output is correct
11 Correct 8 ms 5040 KB Output is correct
12 Correct 5 ms 5036 KB Output is correct
13 Correct 8 ms 5076 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 5 ms 5076 KB Output is correct
16 Correct 6 ms 5076 KB Output is correct
17 Correct 5 ms 5076 KB Output is correct
18 Correct 7 ms 5032 KB Output is correct
19 Correct 6 ms 5092 KB Output is correct
20 Correct 11 ms 5076 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 30 ms 9772 KB Output is correct
23 Correct 21 ms 9100 KB Output is correct
24 Correct 30 ms 9772 KB Output is correct
25 Correct 21 ms 9044 KB Output is correct
26 Correct 48 ms 12184 KB Output is correct
27 Correct 19 ms 8900 KB Output is correct
28 Correct 48 ms 12204 KB Output is correct
29 Correct 19 ms 9008 KB Output is correct
30 Correct 29 ms 9548 KB Output is correct
31 Correct 19 ms 9004 KB Output is correct
32 Correct 21 ms 9044 KB Output is correct
33 Correct 21 ms 9016 KB Output is correct
34 Correct 22 ms 9464 KB Output is correct
35 Correct 23 ms 9452 KB Output is correct
36 Correct 768 ms 9300 KB Output is correct
37 Correct 1030 ms 9056 KB Output is correct
38 Correct 1107 ms 9148 KB Output is correct
39 Correct 460 ms 9256 KB Output is correct
40 Correct 1211 ms 9132 KB Output is correct
41 Correct 2176 ms 12184 KB Output is correct
42 Correct 2628 ms 12312 KB Output is correct
43 Correct 1266 ms 9040 KB Output is correct
44 Correct 1433 ms 8964 KB Output is correct
45 Correct 764 ms 9432 KB Output is correct
46 Correct 1077 ms 9664 KB Output is correct
47 Correct 1235 ms 9136 KB Output is correct
48 Correct 625 ms 8980 KB Output is correct
49 Correct 1464 ms 9088 KB Output is correct
50 Correct 882 ms 9452 KB Output is correct
51 Correct 3152 ms 9796 KB Output is correct
52 Correct 3708 ms 9828 KB Output is correct
53 Correct 3 ms 4948 KB Output is correct
54 Execution timed out 4054 ms 11616 KB Time limit exceeded
55 Halted 0 ms 0 KB -