oj.uz

Submission #234415

# Submission time Handle Problem Language Result Execution time Memory
234415 2020-05-24T07:19:07 Z Vimmer Deda (COCI17_deda) C++14
140 / 140
 124 ms 4604 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define sz(x) ll(x.size())
#define base 1000000
#define M ll(1e9+7)
#define N 200005
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int t[N * 4];

void upd(int v, int tl, int tr, int pos, int val)
{
    if (tl == tr) t[v] = val;
    else
    {
        int md = (tl + tr) >> 1;

        if (pos <= md) upd(v + v, tl, md, pos, val);
          else upd(v + v + 1, md + 1, tr, pos, val);

        t[v] = min(t[v + v], t[v + v + 1]);
    }
}

int get(int v, int tl, int tr, int l, int r, int val)
{
    if (tr < l || r < tl || tl > tr || l > r || t[v] > val) return -1;

    if (tl == tr) return tl;

    int md = (tl + tr) >> 1;

    if (t[v + v] > val) return get(v + v + 1, md + 1, tr, l, r, val);

    int c = get(v + v, tl, md, l, r, val);

    if (c == -1) return get(v + v + 1, md + 1, tr, l, r, val);

    return c;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;

    cin >> n >> q;

    for (int i = 0; i < N * 4; i++) t[i] = inf;

    for (int i = 0; i < q; i++)
    {
        char c;

        cin >> c;

        int x, y;

        cin >> x >> y;

        if (c == 'D') cout << get(1, 1, n, y, n, x) << '\n';
          else upd(1, 1, n, y, x);
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 7 ms 3456 KB Output is correct
3 Correct 8 ms 3544 KB Output is correct
4 Correct 100 ms 4604 KB Output is correct
5 Correct 112 ms 4264 KB Output is correct
6 Correct 110 ms 4344 KB Output is correct
7 Correct 124 ms 4472 KB Output is correct