Submission #699118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
699118	2023-02-15T16:37:32 Z	Nguyen_DD	Deda (COCI17_deda)	C++14	140 / 140	101 ms	8944 KB

deda

/*
// author : Nguyen_DD
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
*/
#include <bits/stdc++.h>
#define bit(i,x) (((x) >> (i)) & 1)
#define BUG cerr << "here" << '\n'
#define name "input"
#define z(i, j) ((i - 1) * m + j)
#define ii pair <int, int>
#define MOD 1000000007
using namespace std;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
const int oo = 1e9 + 7;
const ll inf = 1e18 + 5;
const int maxn = 2e5 + 5;
const int N = 2e6 + 5;
const int dx4[4] = {-1, 0, 1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const bool YES = false;
using vi = vector <int>;
using vvi = vector <vi>;
using vii = vector <ii>; 

int n, q;
vi b;

struct node{
	char type;
	int X;
	int A;
};


vector <node> res;

void open(){
	if (fopen(name".inp", "r")){
		freopen(name".inp", "r", stdin);
		//freopen(name".out" ,"w", stdout);
	}
}

struct IT{
	ll st[maxn * 4];

	void build (int id, int l, int r){
		if (l == r){
			st[id] = inf;
			return;
		}

		int mid = (l + r) >> 1;
		build (id * 2, l, mid);
		build (id * 2 + 1, mid + 1, r);

		st[id] = min (st[id * 2], st[id * 2 + 1]);
	}

	void update (int id, int l, int r, int i, ll val){
		if (i > r || l > i)
			return;
		
		if (l == r){
			st[id] = val;
			return;
		}

		int mid = (l + r) >> 1;
		update (id * 2, l, mid, i, val);
		update (id * 2 + 1, mid + 1, r, i, val);

		st[id] = min (st[id * 2], st[id * 2 + 1]);
	}

	ll get (int id , int l, int r, int u, int v){
		if (u > r || l > v)
			return inf;
		
		if (u <= l && r <= v)
			return st[id];
		
		int mid = (l + r) >> 1;
		ll get1 = get (id * 2, l, mid, u, v);
		ll get2 = get (id * 2 + 1, mid + 1, r, u, v);

		return min (get1, get2);
	} 

	ll find (int id, int l, int r, int i, ll P){		
		if (i > r)
			return -1;
		
		if (l == r){
			return l;
		}

		int mid = (l + r) >> 1;
		ll result = -1;

		if (st[id * 2] <= P)
			result = find (id * 2, l, mid, i , P);
		
		if (result == -1 && st[id * 2 + 1] <= P)
			result = find (id * 2 + 1, mid + 1, r, i, P);
		
		return result;
	}
}segtree;



inline void read(){
	cin >> n >> q;
	segtree.build (1, 1, n);
}


inline void init(){

}


inline void solve(){

	while (q--){
		char t;
		cin >> t;
		ll A;
		int B;
		cin >> A >> B;
		if (t == 'M'){
			segtree.update (1, 1, n, B, A);
			// for (int i = 1; i <= n; ++i)
			// 	cout << segtree.get (1, 1, n, i, i) << ' ';
			// cout << '\n';
		}
		else{
			ll res = segtree.find(1, 1, n, B, A);
			cout << res << '\n';
		}
	}

} 

int32_t main(){
	open();
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;

	t = 1;
	if (YES)
		cin >> t;
	for (int _ = 1; _ <= t; ++_){
		// cout << "Case #" << _ << '\n';
		read();
		init();
		solve();
	}

	return 0;
}

Compilation message

deda.cpp: In function 'void open()':
deda.cpp:45:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	73 ms	8944 KB	Output is correct
5	Correct	95 ms	6296 KB	Output is correct
6	Correct	101 ms	8612 KB	Output is correct
7	Correct	85 ms	8780 KB	Output is correct