CSES - Aalto Competitive Programming 2024 - wk4 - Homework - Results
Submission details
Task:Dynamic Range Minimum Queries
Sender:Niilo
Submission time:2024-09-19 10:55:05 +0300
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.45 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define SEG_OP(a,b) min(a, b)

struct Seg {
  static const int N = 1<<18;
  int S[N*2];

  Seg(int x = 0) {
    for (int i = N; i < N*2; ++i) S[i] = x;
    for (int i = N-1; i >= 1; --i) S[i] = SEG_OP(S[i*2], S[i*2+1]);
  }
  void set(int i, int x) {
    i |= N;
    S[i] = x;
    for (i /= 2; i >= 1; i /= 2) {
      S[i] = SEG_OP(S[i*2], S[i*2+1]);
    }
  }
  ll get(int a, int b, ll s = 0) {
    a |= N; b |= N;
    while (a <= b) {
      if (a % 2 == 1) s = SEG_OP(s, ll(S[a++]));
      if (b % 2 == 0) s = SEG_OP(s, ll(S[b--]));
      a /= 2; b /= 2;
    }
    return s;
  }
};

int n, q;
Seg S( 1e9 );

int main() {
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		S.set(i, x);
	}
	for (int i = 0; i < q; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 1) {
			S.set(a-1,b);
		} else {
			cout << S.get(a-1,b-1, 1e9) << '\n';
		}
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
8 80
7 6 4 6 2 9 4 8
2 1 1
2 1 2
2 1 3
...

correct output
7
6
4
4
2
...

user output
7
6
4
4
2
...
Truncated

Test 2

Verdict: ACCEPTED

input
200000 200000
398739055 65343131 699208332 3...

correct output
28609
129890
20378
20378
311522
...

user output
28609
129890
20378
20378
311522
...
Truncated