Submission #642797

#	Time	Username	Problem	Language	Result	Execution time	Memory
642797		Vladth11	The Potion of Great Power (CEOI20_potion)	C++14	38 / 100	3069 ms	115420 KiB

potion

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast, no-stack-protector")
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int NMAX = 100001;
const int VMAX = 101;
const int INF = 2e9;
const int MOD = 1000000007;
const int BLOCK = 447;
const int base = 117;
const int nr_of_bits = 24;
const int inv2 = 500000004;

set <pii> events[NMAX];
set <int> parcurgere;
int ok = 1;
int minim;
int a[NMAX];
int n;

struct Node {
    int l, r, cnt;
};

int cc = 0;
Node nodes[NMAX * 100];

void adauga(int newNode, int node, int l, int r, int val) {
    if(l == r) {
        if(node != -1 && nodes[node].cnt > 0) {
            nodes[newNode].cnt = 0;
        } else {
            nodes[newNode].cnt = 1;
        }
        return;
    }
    int mid = (l + r) / 2;
    int subL = -1, subR = -1;
    if(node != -1) {
        subL = nodes[node].l;
        subR = nodes[node].r;
    }
    if(val <= mid) {
        nodes[newNode].r = subR;
        nodes[cc++] = {-1, -1, 0};
        nodes[newNode].l = cc - 1;
        adauga(nodes[newNode].l, subL, l, mid, val);
    } else {
        nodes[newNode].l = subL;
        nodes[cc++] = {-1, -1, 0};
        nodes[newNode].r = cc - 1;
        adauga(nodes[newNode].r, subR, mid + 1, r, val);
    }
    nodes[newNode].cnt = 0;
    if(nodes[newNode].l != -1)
        nodes[newNode].cnt += nodes[nodes[newNode].l].cnt;
    if(nodes[newNode].r != -1)
        nodes[newNode].cnt += nodes[nodes[newNode].r].cnt;
    if(nodes[newNode].r == -1 || nodes[nodes[newNode].r].cnt == 0)
        nodes[newNode].r = -1;
    if(nodes[newNode].l == -1 || nodes[nodes[newNode].l].cnt == 0)
        nodes[newNode].l = -1;
}

void baga(int node, int l, int r) {
    if(l == r) {
        if(nodes[node].cnt == 1) {
            if(ok) {
                parcurgere.insert(a[l]);
            } else {
                int val = a[l];
                auto it = parcurgere.lower_bound(val);
                if(it != parcurgere.end()) {
                    minim = min(minim, abs((*it) - val));
                }
                it = parcurgere.upper_bound(val);
                if(it != parcurgere.begin()) {
                    it = prev(it);
                    minim = min(minim, abs((*it) - val));
                }
            }
        }
        return;
    }
    int mid = (l + r) / 2;
    if(nodes[node].l != -1)
        baga(nodes[node].l, l, mid);
    if(nodes[node].r != -1)
        baga(nodes[node].r, mid + 1, r);
}

void init(int N, int D, int H[]) {
    n = N;
    for(int i = 0; i < N; i++) {
        a[i] = H[i];
        events[i].insert({0, cc});
        nodes[cc++] = {-1, -1, 0};
    }
}

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < U; i++) {
        int lastA = (*events[A[i]].rbegin()).second;
        int lastB = (*events[B[i]].rbegin()).second;
        events[A[i]].insert({i + 1, cc});
        nodes[cc++] = {-1, -1, 0};
        int index = cc - 1;
        adauga(cc - 1, lastA, 0, n - 1, B[i]);
        events[B[i]].insert({i + 1, cc});
        nodes[cc++] = {-1, -1, 0};
        adauga(cc - 1, lastB, 0, n - 1, A[i]);
    }
}

int question(int x, int y, int v) {
    vector <int> stX, stY;
    parcurgere.clear();
    ok = 1;
    minim = 1e9;
    int lastX = (*prev(events[x].upper_bound({v + 1, 0}))).second;
    int lastY = (*prev(events[y].upper_bound({v + 1, 0}))).second;
    baga(lastX, 0, n - 1);
    if(parcurgere.empty())
        return 1e9;
    ok = 0;
    baga(lastY, 0, n - 1);
    return minim;

}

Compilation message (stderr)

potion.cpp:2:49: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("Ofast, no-stack-protector")
      |                                                 ^
potion.cpp:33:57: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   33 | void adauga(int newNode, int node, int l, int r, int val) {
      |                                                         ^
potion.cpp:70:33: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   70 | void baga(int node, int l, int r) {
      |                                 ^
potion.cpp:97:32: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   97 | void init(int N, int D, int H[]) {
      |                                ^
potion.cpp:106:42: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
  106 | void curseChanges(int U, int A[], int B[]) {
      |                                          ^
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:112:13: warning: unused variable 'index' [-Wunused-variable]
  112 |         int index = cc - 1;
      |             ^~~~~
potion.cpp: At global scope:
potion.cpp:120:33: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
  120 | int question(int x, int y, int v) {
      |                                 ^

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30