Submission #472971

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472971	2021-09-14T16:26:27 Z	_L__	Deda (COCI17_deda)	C++17	100 / 140	1000 ms	4172 KB

deda

// 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 = 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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	8 ms	332 KB	Output is correct
4	Execution timed out	1096 ms	4100 KB	Time limit exceeded
5	Correct	757 ms	2372 KB	Output is correct
6	Correct	916 ms	3816 KB	Output is correct
7	Execution timed out	1038 ms	4172 KB	Time limit exceeded