Submission #375295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375295	2021-03-09T06:58:35 Z	ezdp	Deda (COCI17_deda)	C++17	60 / 140	301 ms	65540 KB

deda

#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 pair<ll, 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 MAXN = 3e5 + 5;

ordered_set segmtree[2 * MAXN];
ll n, q, T = 1;

ll smaller_than(ordered_set &container, ll v){
	return container.order_of_key({v + 1, 0});
}

void upd(int node, int l, int r, int x, int v){
	if(l == r){
		segmtree[node].insert({v, T});
	}
	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].insert({v, T});
	}
}

ll qry(int node, int l, int r, int ql, int qr, int v){
	/// cout << node << " " << l << " " << r << " " << ql << " " << qr << " " << v << endl;
	if(r < ql || qr < l){
		return LLONG_MAX;
	}
	else if(l == r && smaller_than(segmtree[node], v)){
		return l;
	}
	else if(ql <= l && r <= qr){
		int m = (l + r) / 2;
		/// cout << "left: \n"; for(auto [x, y] : segmtree[2 * node + 0]) cout << x << " " << y << endl;
		/// cout << "right:\n"; for(auto [x, y] : segmtree[2 * node + 1]) cout << x << " " << y << endl;
		if(smaller_than(segmtree[2 * node], v))
			return qry(2 * node, l, m, ql, qr, v);
		else if(smaller_than(segmtree[2 * node + 1], v))
			return qry(2 * node + 1, m + 1, r, ql, qr, v);
		else
			return LLONG_MAX;
	}
	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(int x, int v){ upd(1, 1, n, x, v); ++ T; }
ll qry(int x, int v){ return qry(1, 1, n, x, n, v); }

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	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);
			/// for(int i = 1; i <= 4 * n; i ++) { cout << i << ": "; for(auto [x, y] : segmtree[i]) cout << x << " "; cout << endl; }
		}
		if(t == 'D'){
			ll tmp = qry(y, x);
			cout << (tmp == LLONG_MAX ? -1 : tmp) << endl;
		}
	}
}
/**

*/

Subtask #1

60.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	56812 KB	Output is correct
2	Correct	58 ms	56684 KB	Output is correct
3	Correct	76 ms	57452 KB	Output is correct
4	Runtime error	132 ms	65536 KB	Execution killed with signal 11
5	Runtime error	301 ms	65540 KB	Execution killed with signal 9
6	Runtime error	136 ms	65536 KB	Execution killed with signal 11
7	Runtime error	130 ms	65536 KB	Execution killed with signal 11