Submission #860093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
860093	2023-10-11T15:45:23 Z	pctirziu	Deda (COCI17_deda)	C++17	0 / 140	394 ms	9368 KB

deda

#include <iostream>

using namespace std;

const int nmax = 3e5 + 5;
const int valmax = 2e9 + 5;
int aint[nmax * 4];

void update(int node, int st, int dr, int l, int r, int val)
{
    if(st > r or dr < l)
        return ;
    if(st == dr){
        aint[node] = val;
        return;
    }
    int mid = (st + dr) / 2;
    update(node * 2, st, mid, l, r, val);
    update(node * 2 + 1, mid + 1, dr, l, r, val);
    aint[node] = min(aint[2 * node], aint[2 * node + 1]);
}

int query(int node, int st, int dr, int l, int r, int val)
{
    if(st > r or dr < l)
        return -1;
    if(l <= st and dr <= r){
        if(aint[node] > val)
            return -1;
        if(st == dr and aint[node] <= val)
            return st;
        int rasp;
        while(st != dr){
            int mid = (st + dr) / 2;
            if(aint[2 * node] <= val){
                dr = mid;
                rasp = mid;
                node = node * 2;
            }
            else{
                st = mid + 1;
                node = node * 2 + 1;
            }
        }
        return rasp;
    }
    int mid = (st + dr) / 2;
    int rasp = query(node * 2, st, mid, l, r, val);
    if(rasp != -1)
        return rasp;
    return query(node * 2 + 1, mid + 1, dr, l, r, val);
}

int main()
{
    int n, q;
    cin >> n >> q;
    for(int i = 0; i <= 4 * nmax; i++)
        aint[i] = valmax;
    while(q--){
        string s;
        cin >> s;
        if(s == "M"){
            int x, y;
            cin >> x >> y;
            update(1, 1, n, y, y, x);
        }
        else{
            int x, y;
            cin >> x >> y;
            cout << query(1, 1, n, y, n, x) << "\n";
        }
    }
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:59:17: warning: iteration 1200020 invokes undefined behavior [-Waggressive-loop-optimizations]
   59 |         aint[i] = valmax;
      |         ~~~~~~~~^~~~~~~~
deda.cpp:58:22: note: within this loop
   58 |     for(int i = 0; i <= 4 * nmax; i++)
      |                    ~~^~~~~~~~~~~
deda.cpp: In function 'int query(int, int, int, int, int, int)':
deda.cpp:32:13: warning: 'rasp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |         int rasp;
      |             ^~~~

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4952 KB	Output isn't correct
2	Incorrect	2 ms	4956 KB	Output isn't correct
3	Incorrect	9 ms	4952 KB	Output isn't correct
4	Incorrect	394 ms	9360 KB	Output isn't correct
5	Incorrect	316 ms	9316 KB	Output isn't correct
6	Incorrect	333 ms	9272 KB	Output isn't correct
7	Incorrect	354 ms	9368 KB	Output isn't correct