oj.uz

답안 #1039255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039255 2024-07-30T15:33:34 Z Tonyl The Potion of Great Power (CEOI20_potion) C++17
56 / 100
 1713 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto &a : x)
#define all(x) (x).begin(), (x).end()
#define submit(a,b) cout << a << " " << b << endl
#define D(x) //cerr << #x << ": " << x << endl;

vi alln;

struct Treap {
    int num;
    int prio;
    Treap *left = nullptr, *right = nullptr;

    Treap(Treap *t) {
        num = t->num;
        prio = t->prio;
    }

    Treap(int nm, int pr) {
        num = nm;
        prio = pr;
    }

    Treap(int nm) {
        num = nm;
        prio = rand();
    }

    void gather_all() {
        alln.push_back(num);
        if (left != nullptr) left->gather_all();
        if (right != nullptr) right->gather_all();
    }
};

Treap* merge(Treap* left, Treap* right) {
    if (left == nullptr) return right;
    if (right == nullptr) return left;

    if (left->prio <= right->prio) {
        Treap *t = new Treap(left);
        t->left = left->left;
        t->right = merge(left->right, right);
        return t;
    } else {
        Treap *t = new Treap(right);
        t->right = right->right;
        t->left = merge(left, right->left);
        return t;
    }
}

pair<Treap*, Treap*> split(Treap* tr, int num) {
    if (tr == nullptr) return {tr, tr};
    if (tr->num < num) {
        Treap *t = new Treap(tr);
        t->left = tr->left;
        auto p = split(tr->right, num);
        t->right = p.first;
        return {t, p.second};
    } else {
        Treap *t = new Treap(tr);
        t->right = tr->right;
        auto p = split(tr->left, num);
        t->left = p.second;
        return {p.first, t};
    }
}

const int MAX_N = 1e5+2;
Treap* smol[MAX_N];

Treap* flipp(Treap* tr, int num) {
    Treap *lower, *exact, *bigger;
    auto p = split(tr, num);
    lower = p.first;
    auto p2 = split(p.second, num+1);
    exact = p2.first;
    bigger = p2.second;
    if (exact == nullptr) exact = smol[num];
    else exact = nullptr;

    Treap* t = merge(lower, exact);
    return merge(t, bigger);
}

struct TimeTraveller {
    vector<pair<int, Treap*>> history;

    TimeTraveller() {
        history.push_back({-1, nullptr});
    }

    void flip(int i, int time) {
        Treap* c = flipp(history.back().second, i);
        history.push_back({time, c});
    }

    vi get_all(int time) {
        auto p = lower_bound(all(history), pair<int, Treap*>(time+1, nullptr));
        p--;
        if ((*p).second == nullptr) return vi();
        alln = vi();
        (*p).second->gather_all();
        return alln;
    }
};

int n,d;
vi hs;

TimeTraveller fr[MAX_N];

int get_ans(vi a, vi b) {
    int best = 1e9;

    vi h1, h2;
    trav(aa, a) {
        h1.push_back(hs[aa]);
    }
    sort(all(h1));
    trav(bb, b) {
        h2.push_back(hs[bb]);
    }
    sort(all(h2));

    if (h1.size() == 0) return best;

    int i = 0;
    trav(hb, h2) {
        while (h1[i] < hb && i != h1.size()-1) i++;
        best = min(best, abs(hb - h1[i]));
        if (i!=0) best = min(best, abs(hb - h1[i-1]));
    }

    return best;
}

void init(int N, int D, int H[]) {
    srand(43249);
    n = N; d = D;
    REP(i,n) hs.push_back(H[i]);
    REP(i,n) smol[i] = new Treap(i, rand());
}

void curseChanges(int U, int A[], int B[]) {
    REP(uu, U) {
        int a = A[uu];
        int b = B[uu];
        fr[a].flip(b, uu+1);
        fr[b].flip(a, uu+1);
    }
}

int question(int x, int y, int v) {
    return get_ans(fr[x].get_all(v), fr[y].get_all(v));
}

Compilation message

potion.cpp: In function 'int get_ans(vi, vi)':
potion.cpp:136:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         while (h1[i] < hb && i != h1.size()-1) i++;
      |                              ~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5720 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5976 KB Output is correct
2 Correct 6 ms 6088 KB Output is correct
3 Correct 6 ms 5976 KB Output is correct
4 Correct 16 ms 10704 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 65788 KB Output is correct
2 Correct 255 ms 65756 KB Output is correct
3 Correct 231 ms 135272 KB Output is correct
4 Runtime error 352 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 65812 KB Output is correct
2 Correct 1482 ms 194552 KB Output is correct
3 Correct 996 ms 173740 KB Output is correct
4 Correct 1561 ms 196424 KB Output is correct
5 Correct 325 ms 78508 KB Output is correct
6 Correct 1713 ms 196040 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 8024 KB Output is correct
2 Correct 69 ms 12120 KB Output is correct
3 Correct 109 ms 11156 KB Output is correct
4 Correct 635 ms 14028 KB Output is correct
5 Correct 633 ms 11644 KB Output is correct
6 Correct 93 ms 12120 KB Output is correct
7 Correct 501 ms 13912 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5720 KB Output is correct
2 Correct 6 ms 5976 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 6 ms 5976 KB Output is correct
5 Correct 16 ms 10704 KB Output is correct
6 Correct 256 ms 65788 KB Output is correct
7 Correct 255 ms 65756 KB Output is correct
8 Correct 231 ms 135272 KB Output is correct
9 Runtime error 352 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -