oj.uz

Submission #642813

# Submission time Handle Problem Language Result Execution time Memory
642813 2022-09-20T14:59:15 Z Vladth11 The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 115364 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#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[2];
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(nodes[node].cnt == 0) return;
    if(l == r) {
        parcurgere[ok].push_back(a[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) {
    ok = 0;
    parcurgere[0].clear();
    parcurgere[1].clear();
    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[0].empty())
        return 1e9;
    ok = 1;
    baga(lastY, 0, n - 1);
    sort(parcurgere[0].begin(), parcurgere[0].end());
    sort(parcurgere[1].begin(), parcurgere[1].end());
    int i = 0, j = 0;
    while(i < parcurgere[0].size() && j < parcurgere[1].size()){
        minim = min(minim, abs(parcurgere[0][i] - parcurgere[1][j]));
        if(parcurgere[0][i] > parcurgere[1][j]){
            j++;
        }else{
            i++;
        }
    }
    return minim;
 
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:98:13: warning: unused variable 'index' [-Wunused-variable]
   98 |         int index = cc - 1;
      |             ^~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:121:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     while(i < parcurgere[0].size() && j < parcurgere[1].size()){
      |           ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:121:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     while(i < parcurgere[0].size() && j < parcurgere[1].size()){
      |                                       ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5456 KB Output is correct
2 Correct 4 ms 5328 KB Output is correct
3 Correct 4 ms 5384 KB Output is correct
4 Correct 24 ms 12116 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 115088 KB Output is correct
2 Correct 487 ms 115072 KB Output is correct
3 Correct 443 ms 115364 KB Output is correct
4 Execution timed out 3054 ms 76872 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 115040 KB Output is correct
2 Execution timed out 3040 ms 115204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10064 KB Output is correct
2 Correct 142 ms 10064 KB Output is correct
3 Correct 253 ms 10064 KB Output is correct
4 Correct 1473 ms 10084 KB Output is correct
5 Correct 1337 ms 10100 KB Output is correct
6 Correct 187 ms 8656 KB Output is correct
7 Correct 1240 ms 10124 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 4 ms 5456 KB Output is correct
3 Correct 4 ms 5328 KB Output is correct
4 Correct 4 ms 5384 KB Output is correct
5 Correct 24 ms 12116 KB Output is correct
6 Correct 511 ms 115088 KB Output is correct
7 Correct 487 ms 115072 KB Output is correct
8 Correct 443 ms 115364 KB Output is correct
9 Execution timed out 3054 ms 76872 KB Time limit exceeded
10 Halted 0 ms 0 KB -