답안 #922214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922214	2024-02-05T08:48:34 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	459 ms	6572 KB

deda

//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int inf = 1e9 + 7;
struct SEGT{
    vector < int > t;
    int tree_size;
    const int identity_element = inf;
    int merge(int x , int y){ 
        return min(x,y);
    }
    void init(int x){
        tree_size = x+3;
        t.assign(2*tree_size , identity_element);
    }
    void modify(int p, int value) {  // set value at position p
        for (t[p += tree_size] = value; p > 1; p >>= 1){
            t[p>>1] = merge(t[p] , t[p^1]); 
        }
    }
    int query(int l, int r) {  // sum on interval [l, r]
        int res = identity_element;
        for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = merge(res , t[l++]); 
            if (r&1) res = merge(res , t[--r]); 
        }
        return res;
    }
} segt;
void solve(){
	int n,q;
	cin >> n >> q;
	segt.init(n);
	while(q--){
		char ty;
		int x,y;
		cin >> ty >> x >> y;
		if(ty == 'M'){
			segt.modify(y , x);
		}
		else{
			int l = y , r = n+1;
			while(l < r){
				int mid = (l + r) >> 1;
				int q1 = segt.query(l , mid);
				int q2 = segt.query(mid+1 , r);
				// cout << l << " " << mid << " " << r << " : " << q1 << " " << q2  << endl;
				if(q1 <= x){
					r = mid;
				}
				else {
					l = mid+1;
				}
			}
			cout << (l == n+1 ? -1 : l) << endl;
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Compilation message

deda.cpp: In function 'void solve()':
deda.cpp:48:9: warning: unused variable 'q2' [-Wunused-variable]
   48 |     int q2 = segt.query(mid+1 , r);
      |         ^~

Subtask #1

140.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	7 ms	532 KB	Output is correct
4	Correct	459 ms	6572 KB	Output is correct
5	Correct	299 ms	5200 KB	Output is correct
6	Correct	343 ms	5700 KB	Output is correct
7	Correct	375 ms	6232 KB	Output is correct