Submission #640093

#	Time	Username	Problem	Language	Result	Execution time	Memory
640093		Moses	Deda (COCI17_deda)	C++14	140 / 140	145 ms	7884 KiB

deda

/*
           _                   _         _       __  __  _____ 
     /\   | |            /\   | |       | |     |  \/  |/ ____|
    /  \  | |__   ___   /  \  | |__   __| | ___ | \  / | |     
   / /\ \ | '_ \ / _ \ / /\ \ | '_ \ / _` |/ _ \| |\/| | |     
  / ____ \| |_) | (_) / ____ \| |_) | (_| | (_) | |  | | |____ 
 /_/    \_\_.__/ \___/_/    \_\_.__/ \__,_|\___/|_|  |_|\_____|
*/

// build command:
// g++ -o "exe" "%f" -Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector -D LOCAL -Wno-unused-result

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

// -------------------------<RNG>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.

int getrand(int l,int r) {
	return uniform_int_distribution<int>(l, r)(RNG);
}

const ld eps = 1e-9;
const int mod = 1e9 + 7;
const int oo = 1e9 + 7;
const ll lloo = 1e18 + 7;
const int N = 1e6 + 7;

int n,q;

struct node {
	int mn;
	node(int _mn = oo) : mn(_mn) {}
};

struct ST {
	#define lc (id<<1)
	#define rc ((id<<1)|1)
	#define mid (l+(r-l)/2)

	vector<node> seg;
	ST() {seg.resize(n*4);}

	inline node merge(node left,node right) {
		node ret;
		ret.mn = (left.mn < right.mn) ? left.mn:right.mn;
		return ret;
	}

	inline void pull(int id) {
		seg[id] = merge(seg[lc],seg[rc]);
	}

	void build(int l = 0,int r = n-1,int id = 1) {
		if (l == r) {
			seg[id].mn = oo;
			return;
		}
		build(l,mid,lc);
		build(mid+1,r,rc);
		pull(id);
	}

	void upd(int i,int x,int l = 0,int r = n-1,int id = 1) {
		if (l == r) {
			seg[id] = node(x);
			return;
		}
		if (i <= mid) upd(i,x,l,mid,lc);
		else upd(i,x,mid+1,r,rc);
		pull(id);
	}

	int query(int y,int b,int l = 0,int r = n-1,int id = 1) {
		dbg(l,r,y,b);
		if (r < b) return -1;
		if (l < b) {
			int ret1 = query(y,b,l,mid,id*2);
			if (ret1 != -1) return ret1;
			return query(y,b,mid+1,r,id*2+1);
		}
		if (l == r) return (seg[id].mn <= y) ? l+1:-1;
		if (seg[id*2].mn <= y) return query(y,b,l,mid,id*2);
		return query(y,b,mid+1,r,id*2+1);
	}
};

void solve() {
	scanf("%d %d",&n,&q);
	ST segtree;
	segtree.build();
	
	for(int j = 0 ; j < q ; j++) {
		char t;
		scanf(" %c",&t);
		if (t == 'M') {
			int x,a;
			scanf("%d %d",&x,&a);
			a--;
			segtree.upd(a,x);
		} else if (t == 'D') {
			int y,b;
			scanf("%d %d",&y,&b);
			b--;
			printf("%d\n",segtree.query(y,b));
		}
	}
}

int main() {
	// freopen("in","r",stdin);
	// freopen("out","w",stdout);
	int T = 1;
	//scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Compilation message (stderr)

deda.cpp: In function 'void solve()':
deda.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d %d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
deda.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |   scanf(" %c",&t);
      |   ~~~~~^~~~~~~~~~
deda.cpp:125:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |    scanf("%d %d",&x,&a);
      |    ~~~~~^~~~~~~~~~~~~~~
deda.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |    scanf("%d %d",&y,&b);
      |    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 140 / 140