Submission #472973

#	Time	Username	Problem	Language	Result	Execution time	Memory
472973		_L__	Deda (COCI17_deda)	C++17	100 / 140	1081 ms	5092 KiB

deda

// This code is written by _L__
#include <bits/stdc++.h>
using namespace std;
#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 int mod = 1e9+7, N = 2e5+13, inf = 1e9+1;
const ld E = 1e-6;
#define ff first
#define ss second

int 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]);
}
int 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));
}

int lower(int l, int r, int y){
    int n = r;
    int ans = -1;
    while(l<=r){
        int mid = (l+r)/2;
        int 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);
    int a[n] = {};
    while(q--){
        char c; cin >> c;
        if(c == 'M'){
            int x; int i; cin >> x >> i;
            a[i] = x;
            update(1,1,n,i,x);
        } else {
            int b, y; cin >> y >> b;
            int x = lower(b,n,y);
            cout << x << endl;
        }
    }
}

• Subtask 1: 100 / 140