oj.uz

Submission #410676

# Submission time Handle Problem Language Result Execution time Memory
410676 2021-05-23T10:36:06 Z dynam1c Bridges (APIO19_bridges) C++17
16 / 100
 262 ms 3732 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

struct RMQ {
	int n;
	vector<int> seg;
	RMQ(vector<int> arr) : n(arr.size()), seg(2*n) {
		for (int i = 0; i < n; i++)
			seg[i+n] = arr[i];
		for (int i = n-1; i > 0; i--)
			seg[i] = min(seg[i<<1], seg[i<<1|1]);
	}
	int query(int l, int r) {
		int acc = INT_MAX;
		for (l += n, r += n; l != r; l >>= 1, r >>= 1) {
			if (l&1) acc = min(acc, seg[l++]);
			if (r&1) acc = min(acc, seg[--r]);
		}
		return acc;
	}
	void update(int i, int x) {
		for (seg[i += n] = x; i > 1; i >>= 1)
			seg[i>>1] = min(seg[i], seg[i^1]);
	}
};

constexpr int L = 16;
signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, q;
	cin >> n >> m;
	vector<int> ws(m);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y >> ws[i];
	}
	cin >> q;
	RMQ rmq(ws);
	for (int qq = 0; qq < q; qq++) {
		int t, x, y;
		cin >> t >> x >> y;
		x--;
		if (t == 1) {
			rmq.update(x, y);
		} else {
			int l = x, r = x;
			for (int i = L-1; i >= 0; i--) {
				int d = 1<<i;
				if (r+d <= m and rmq.query(x, r+d) >= y)
					r += d;
				if (l-d >= 0 and rmq.query(l-d, x) >= y)
					l -= d;
			}
			cout << r-l+1 << endl;
		}
	}
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1340 KB Output is correct
2 Correct 110 ms 1032 KB Output is correct
3 Correct 110 ms 1100 KB Output is correct
4 Correct 113 ms 1100 KB Output is correct
5 Correct 112 ms 1036 KB Output is correct
6 Correct 179 ms 1088 KB Output is correct
7 Correct 168 ms 1088 KB Output is correct
8 Correct 164 ms 1100 KB Output is correct
9 Correct 40 ms 1732 KB Output is correct
10 Correct 122 ms 2696 KB Output is correct
11 Correct 112 ms 2688 KB Output is correct
12 Correct 262 ms 3732 KB Output is correct
13 Correct 75 ms 3632 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 1216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 2120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1340 KB Output is correct
2 Correct 110 ms 1032 KB Output is correct
3 Correct 110 ms 1100 KB Output is correct
4 Correct 113 ms 1100 KB Output is correct
5 Correct 112 ms 1036 KB Output is correct
6 Correct 179 ms 1088 KB Output is correct
7 Correct 168 ms 1088 KB Output is correct
8 Correct 164 ms 1100 KB Output is correct
9 Correct 40 ms 1732 KB Output is correct
10 Correct 122 ms 2696 KB Output is correct
11 Correct 112 ms 2688 KB Output is correct
12 Correct 262 ms 3732 KB Output is correct
13 Correct 75 ms 3632 KB Output is correct
14 Incorrect 101 ms 1216 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -