#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];
vector <int> parcurgere;
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) {
parcurgere.push_back(l);
}
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();
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);
stX = parcurgere;
parcurgere.clear();
baga(lastY, 0, n - 1);
stY = parcurgere;
int minim = 1e9;
if(stX.size() == 0 || stY.size() == 0)
return minim;
set <int> nou;
for(auto p : stX) {
nou.insert(a[p]);
}
assert(stX.size() <= 500);
assert(stY.size() <= 500);
for(auto p : stY) {
int val = a[p];
auto it = nou.lower_bound(val);
if(it != nou.end()) {
minim = min(minim, abs((*it) - val));
}
it = nou.upper_bound(val);
if(it != nou.begin()) {
it = prev(it);
minim = min(minim, abs((*it) - val));
}
}
return minim;
}
Compilation message
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:31:57: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
31 | void adauga(int newNode, int node, int l, int r, int val) {
| ^
potion.cpp:68:33: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
68 | void baga(int node, int l, int r) {
| ^
potion.cpp:82:32: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
82 | void init(int N, int D, int H[]) {
| ^
potion.cpp:91:42: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
91 | void curseChanges(int U, int A[], int B[]) {
| ^
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:97:13: warning: unused variable 'index' [-Wunused-variable]
97 | int index = cc - 1;
| ^~~~~
potion.cpp: At global scope:
potion.cpp:105:33: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
105 | int question(int x, int y, int v) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5328 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5328 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5456 KB |
Output is correct |
| 4 |
Correct |
26 ms |
12124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
569 ms |
115032 KB |
Output is correct |
| 2 |
Correct |
522 ms |
115100 KB |
Output is correct |
| 3 |
Correct |
489 ms |
115380 KB |
Output is correct |
| 4 |
Execution timed out |
3084 ms |
77028 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
485 ms |
115172 KB |
Output is correct |
| 2 |
Execution timed out |
3087 ms |
115444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
10064 KB |
Output is correct |
| 2 |
Correct |
174 ms |
10064 KB |
Output is correct |
| 3 |
Correct |
293 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
2078 ms |
10104 KB |
Output is correct |
| 5 |
Correct |
2021 ms |
10152 KB |
Output is correct |
| 6 |
Correct |
228 ms |
8656 KB |
Output is correct |
| 7 |
Correct |
1661 ms |
10136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5328 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5328 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5456 KB |
Output is correct |
| 5 |
Correct |
26 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
569 ms |
115032 KB |
Output is correct |
| 7 |
Correct |
522 ms |
115100 KB |
Output is correct |
| 8 |
Correct |
489 ms |
115380 KB |
Output is correct |
| 9 |
Execution timed out |
3084 ms |
77028 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
