oj.uz

Submission #375318

# Submission time Handle Problem Language Result Execution time Memory
375318 2021-03-09T07:35:32 Z ezdp Deda (COCI17_deda) C++14
140 / 140
 786 ms 9120 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;
#define row vector<ll>
#define row_matrix vector<ll>
#define matrix vector<row_matrix>
#define ordered_set_T ll

using namespace std;
using namespace __gnu_pbds;

typedef tree<ordered_set_T, null_type, less<ordered_set_T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are smaller than x
/// insert(x)		 -> inserts x into the set

const ll INF = 1e9 + 9;
const ll MAXN = 262200;

ll segmtree[2 * MAXN], n, q;

void upd(int node, int l, int r, int x, int v){
	if(l == r){
		segmtree[node] = v;
	}
	else{
		int m = (l + r) / 2;
		if(l <= x && x <= m)
			upd(2 * node, l, m, x, v);
		else 
			upd(2 * node + 1, m + 1, r, x, v);
		segmtree[node] = min(segmtree[2 * node], segmtree[2 * node + 1]);
	}
}

ll qry(int node, int l, int r, int ql, int qr, int v){
	if(r < ql || qr < l){
		return INF;
	}
	else if(l == r && segmtree[node] <= v){
		return l;
	}
	else if(ql <= l && r <= qr){
		if(segmtree[node] <= v){
			int m = (l + r) / 2;
			int tmp = qry(2 * node, l, m, ql, qr, v);
			return (tmp == INF ? qry(2 * node + 1, m + 1, r, ql, qr, v) : tmp);
		}
		else 
			return INF;
	}
	else{
		int m = (l + r) / 2;
		ll q1 = qry(2 * node, l, m, ql, qr, v);
		ll q2 = qry(2 * node + 1, m + 1, r, ql, qr, v);
		return min(q1, q2);
	}
}

void upd(ll x, ll v){ upd(1, 1, n, x, v); }
ll qry(ll x, ll v) { return qry(1, 1, n, x, n, v); }

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	for(int i = 0; i < 2 * MAXN; i ++) segmtree[i] = INF;
	cin >> n >> q;
	for(int i = 0; i < q; i ++){
		char t; int x, y; cin >> t >> x >> y;
		if(t == 'M'){
			upd(y, x);
		}
		if(t == 'D'){
			int tmp = qry(y, x);
			cout << (tmp == INF ? -1 : tmp) << endl;
		}
	}
}
/**

*/

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4460 KB Output is correct
2 Correct 4 ms 4460 KB Output is correct
3 Correct 16 ms 4460 KB Output is correct
4 Correct 786 ms 9120 KB Output is correct
5 Correct 642 ms 8500 KB Output is correct
6 Correct 691 ms 8700 KB Output is correct
7 Correct 730 ms 8940 KB Output is correct