oj.uz

답안 #472946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472946 2021-09-14T15:43:25 Z _L__ Deda (COCI17_deda) C++17
100 / 140
 1000 ms 8920 KB 
// This code is written by _L__
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;
#define endl '\n'
#define F_word ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
typedef long long ll;
typedef long double ld;
const ll mod = 1e9+7, N = 2e5+13, inf = 1e18;
const ld E = 1e-6;
#define ff first
#define ss second

ll t[4*N];

void build(int v, int tl, int tr){
    if(tl>tr)return;
    if(tl == tr){t[v] = inf; return;}
    int tm = (tl+tr)/2;
    build(v*2, tl, tm);
    build(v*2+1, tm+1, tr);
    t[v] = min(t[v*2], t[v*2+1]);
}
void update(int v, int tl, int tr, int idx, int rx){
    if(tl > tr) return;
    if(tl == tr){t[v] = rx; return;}
    int tm = (tl+tr)/2;
    if(idx > tm) update(v*2+1, tm+1, tr, idx, rx);
    else update(v*2, tl, tm, idx, rx);
    t[v] = min(t[v*2], t[v*2+1]);
}
ll query(int v, int tl, int tr, int l, int r){
    if(tl > tr) return inf;
    if(l > tr || r < tl) return inf;
    if(tl == l && tr == r) return t[v];
    int tm = (tl+tr)/2;
    return min(query(v*2, tl, tm, l, min(tm, r)), query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

ll lower(int l, int r, ll y){
    int n = r;
    ll ans = -1;
    while(l<=r){
        ll mid = (l+r)/2;
        ll x = query(1,1,n,l,mid);
        if(x <= y){
            ans = mid;
            r = mid-1;
        } else l = mid+1;
    }
    return ans;
}

int main(void){
    F_word;
    int n, q; cin >> n >> q;
    build(1, 1, n);
    ll a[n] = {};
    while(q--){
        char c; cin >> c;
        if(c == 'M'){
            ll x; int i; cin >> x >> i;
            a[i] = x;
            update(1,1,n,i,x);
        } else {
            ll b, y; cin >> y >> b;
            ll x = lower(b,n,y);
            cout << x << endl;
        }
    }
}

Subtask #1
100.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Execution timed out 1099 ms 7508 KB Time limit exceeded
5 Correct 785 ms 6092 KB Output is correct
6 Correct 966 ms 8564 KB Output is correct
7 Execution timed out 1080 ms 8920 KB Time limit exceeded