oj.uz

Submission #573561

# Submission time Handle Problem Language Result Execution time Memory
573561 2022-06-06T19:57:25 Z redstonegamer22 The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 238972 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 7;

template < const int L, const int R >
struct DynPersSegTreeSet {
    struct Node {
        int val;
        Node *left, *right;

        Node(int _val, Node *_left, Node *_right) { val = _val; left = _left; right = _right; }
        Node(const Node &oth) { val = oth.val; left = oth.left; right = oth.right; }
        Node() { val = 0; left = right = nullptr; }
    };

    inline static Node nullish;

    Node* _update(Node *cnt, int l, int r, int poz, bool to_insert) {
        if(l == r) return (to_insert ? (new Node(1, &nullish, &nullish)) : &nullish);

        Node *ret_node = new Node(*cnt);

        int mid = (l + r) / 2;
        if(poz <= mid) ret_node->left = _update(ret_node->left, l, mid, poz, to_insert);
        else ret_node->right = _update(ret_node->right, mid + 1, r, poz, to_insert);

        ret_node->val = ret_node->left->val + ret_node->right->val;

        return ret_node;
    }

    int _query(Node *cnt, int l, int r, int poz) {
        if(l == r) return cnt->val != 0;

        int mid = (l + r) / 2;
        if(poz <= mid) return _query(cnt->left, l, mid, poz);
        else return _query(cnt->right, mid + 1, r, poz);
    }

    Node *head;
    DynPersSegTreeSet() {
        nullish = Node(0, &nullish, &nullish);
        head = &nullish;
    }

    void change(int x) {
        bool is_friend = _query(head, L, R, x);
        head = _update(head, L, R, x, !is_friend);
    }

    void put_all(Node *cnt, int l, int r, vector<int>& v) {
        if(cnt->val == 0) return;
        if(l == r) { v.push_back(l); return; }

        int mid = (l + r) / 2;
        put_all(cnt->left, l, mid, v);
        put_all(cnt->right, mid + 1, r, v);

        return;
    }

    vector<int> get_all() {
        vector<int> ret; ret.reserve(head->val);
        put_all(head, L, R, ret);

        return ret;
    }
};
using PersSet = DynPersSegTreeSet<0, NMAX>;

struct Shaman {
    vector<pair<int, PersSet>> friends;

    Shaman() {
        friends.push_back({0, PersSet()});
    }

    void change(int day, int oth) {
        PersSet next_friends = friends.back().second;
        next_friends.change(oth);

        friends.push_back({day, next_friends});
    }

    vector<int> get_friends(int day) {
        int ans = 0, step = 1;
        while(step < friends.size()) step *= 2;
        for(; step > 0; step /= 2) {
            if(ans + step < friends.size() && friends[ans + step].first <= day) ans += step;
        }
        return friends[ans].second.get_all();
    }
} shamans[NMAX];

int heights[NMAX];

void init(int n, int d, int h[]) {
    for(auto &s : shamans) s = Shaman();
    for(int i = 0; i < n; i++) heights[i] = h[i];
}

void curseChanges(int u, int a[], int b[]) {
    for(int day = 1; day <= u; day++) {
        int x, y; x = a[day - 1]; y = b[day - 1];
        shamans[x].change(day, y);
        shamans[y].change(day, x);
    }
}

int question(int x, int y, int day) {

    auto vecx = shamans[x].get_friends(day);
    for(auto &e : vecx) e = heights[e];
    sort(vecx.begin(), vecx.end());

    auto vecy = shamans[y].get_friends(day);
    for(auto &e : vecy) e = heights[e];
    sort(vecy.begin(), vecy.end());

    #ifdef DEBUG
        cerr << "VECX: "; for(auto e : vecx) cerr << e << " "; cerr << endl;
        cerr << "VECY: "; for(auto e : vecy) cerr << e << " "; cerr << endl;

        cerr << endl << endl;
    #endif // DEBUG

    int min_dist = 1e9;
    for(auto xf : vecx) {
        int yind = static_cast<int>(lower_bound(vecy.begin(), vecy.end(), xf) - vecy.begin());

        if(yind < vecy.size()) min_dist = min(min_dist, vecy[yind] - xf);
        if(yind - 1 >= 0) min_dist = min(min_dist, xf - vecy[yind - 1]);
    }

    return min_dist;
}

Compilation message

potion.cpp: In member function 'std::vector<int> Shaman::get_friends(int)':
potion.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, DynPersSegTreeSet<0, 100007> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         while(step < friends.size()) step *= 2;
      |               ~~~~~^~~~~~~~~~~~~~~~
potion.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, DynPersSegTreeSet<0, 100007> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             if(ans + step < friends.size() && friends[ans + step].first <= day) ans += step;
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:134:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         if(yind < vecy.size()) min_dist = min(min_dist, vecy[yind] - xf);
      |            ~~~~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5712 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6864 KB Output is correct
2 Correct 11 ms 6964 KB Output is correct
3 Correct 11 ms 6864 KB Output is correct
4 Correct 22 ms 7716 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 238868 KB Output is correct
2 Correct 692 ms 238972 KB Output is correct
3 Correct 497 ms 230724 KB Output is correct
4 Execution timed out 3056 ms 234000 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 238908 KB Output is correct
2 Execution timed out 3056 ms 232684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 17352 KB Output is correct
2 Correct 190 ms 17180 KB Output is correct
3 Correct 294 ms 17156 KB Output is correct
4 Correct 1747 ms 17220 KB Output is correct
5 Correct 1641 ms 17364 KB Output is correct
6 Correct 240 ms 17364 KB Output is correct
7 Correct 1429 ms 17128 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5712 KB Output is correct
2 Correct 11 ms 6864 KB Output is correct
3 Correct 11 ms 6964 KB Output is correct
4 Correct 11 ms 6864 KB Output is correct
5 Correct 22 ms 7716 KB Output is correct
6 Correct 700 ms 238868 KB Output is correct
7 Correct 692 ms 238972 KB Output is correct
8 Correct 497 ms 230724 KB Output is correct
9 Execution timed out 3056 ms 234000 KB Time limit exceeded
10 Halted 0 ms 0 KB -