oj.uz

Submission #1002515

# Submission time Handle Problem Language Result Execution time Memory
1002515 2024-06-19T15:43:31 Z yoav_s The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 260968 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef int ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e9;
const ll mod = 1e9 + 7;
ll D;
struct Node
{
    Node *l, *r;
    short val;
    ll left, right;
    Node()
    {
        l = r = NULL;
        val = left = right = 0;
    }
    Node(ll size, ll offset)
    {
        ll act = pow(2, ceil(log2(size)));
        left = offset; right = offset + act - 1;
        val = 0;
        if (act > 1)
        {
            l = new Node(act / 2, offset);
            r = new Node(act / 2, offset + act / 2);
        }
    }
    Node(ll size) : Node(size, 0) {}
    Node(Node *l, Node *r, ll val, ll left, ll right)
    {
        this->l = l;
        this->r = r;
        this->val = val;
        this->left = left;
        this->right = right;
    }
    Node(Node *l, Node *r)
    {
        this->l = l;
        this->r = r;
        this->val = l->val + r->val;
        this->left = l->left;
        this->right = r->right;
    }
    Node *update(ll index, short val)
    {
        if (left == right)
        {
            return new Node(NULL, NULL, val, index, index);
        }
        ll mid = (left + right) / 2;
        Node *curL = l, *curR = r;
        if (index <= mid)
        {
            curL = l->update(index, val);
        }
        else
        {
            curR = r->update(index, val);
        }
        return new Node(curL, curR);
    }
    void toList(v &arr)
    {
        if (val == 0 || arr.size() >= D) return;
        if (left == right)
        {
            arr.pb(left);
            return;
        }
        l->toList(arr);
        r->toList(arr);
    }
};

ll N;
v H;
ll U;
vv sometimesNeighbors;
vp edges;
vector<vector<pair<ll, Node*>>> trees;
vector<map<ll, ll>> neighborShrink;

void init(int gN, int gD, int gH[]) {
    N = gN;
    D = gD;
    for (ll i= 0 ; i < N; i++) H.pb(gH[i]);
}

void curseChanges(int gU, int A[], int B[]) {
    U = gU;
    sometimesNeighbors.resize(N);
    for (ll i = 0; i < U; i++)
    {
        edges.eb(A[i], B[i]);
        sometimesNeighbors[A[i]].pb(B[i]);
        sometimesNeighbors[B[i]].pb(A[i]);
    }
    trees.resize(N);
    vvb areNeighbors(N);
    neighborShrink.resize(N);
    for (ll i = 0; i < N; i++)
    {
        sort(all(sometimesNeighbors[i]));
        sometimesNeighbors[i].erase(unique(all(sometimesNeighbors[i])),sometimesNeighbors[i].end());
        sort(all(sometimesNeighbors[i]),[](ll i, ll j){return H[i] < H[j];});
        for (ll j = 0; j < sometimesNeighbors[i].size(); j++)
        {
            neighborShrink[i][sometimesNeighbors[i][j]] = j;
        }
        trees[i].eb(0, new Node(sometimesNeighbors[i].size()));
        areNeighbors[i].resize(sometimesNeighbors[i].size());
    }
    for (ll iter = 0; iter < U; iter++)
    {
        ll j1 = neighborShrink[edges[iter].f][edges[iter].s];
        ll i1 = edges[iter].f;
        ll i2 = edges[iter].s, j2 = neighborShrink[edges[iter].s][edges[iter].f];
        if (areNeighbors[i1][j1])
        {
            areNeighbors[i1][j1] = false;
            areNeighbors[i2][j2] = false;
            trees[i1].eb(iter + 1, trees[i1].back().s->update(j1, 0));
            trees[i2].eb(iter + 1, trees[i2].back().s->update(j2, 0));
        }
        else
        {
            areNeighbors[i1][j1] = true;
            areNeighbors[i2][j2] = true;
            trees[i1].eb(iter + 1, trees[i1].back().s->update(j1, 1));
            trees[i2].eb(iter + 1, trees[i2].back().s->update(j2, 1));
        }
    }
}

int question(int x, int y, int time) {
    auto cmp = [](pair<ll, Node *> x, pair<ll, Node*> y){return x.f < y.f || (x.f == y.f && y.s == NULL);};
    Node *xNeighbors = (*(upper_bound(all(trees[x]), pair<ll, Node*>(time, NULL), cmp) - 1)).s;
    Node *yNeighbors = (*(upper_bound(all(trees[y]), pair<ll, Node*>(time, NULL), cmp) - 1)).s;
    v xNeighborsArr, yNeighborsArr;
    xNeighbors->toList(xNeighborsArr);
    yNeighbors->toList(yNeighborsArr);
    short i = 0, j = 0;
    ll mini = INF;
    while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
    {
        ll iHeight = H[sometimesNeighbors[x][xNeighborsArr[i]]];
        while (j < (ll)yNeighborsArr.size() - 1 && H[sometimesNeighbors[y][yNeighborsArr[j + 1]]] <= iHeight) j++;
        mini = min(mini, abs(iHeight - H[sometimesNeighbors[y][yNeighborsArr[j]]]));
        if (j < yNeighborsArr.size() - 1) mini = min(mini, abs(iHeight - H[sometimesNeighbors[y][yNeighborsArr[j + 1]]]));
        i++;
    }
    return mini;
}
/*
int main() {
  int N, D, U, Q;
  std::ios::sync_with_stdio(false); std::cin.tie(NULL);
  std::cin >> N >> D >> U >> Q;

  int *F = new int[N];
  for (int i=0; i<N; i++)
    std::cin >> F[i];
  init(N, D, F);

  int *A = new int[U], *B = new int[U];
  for (int i=0; i<U; i++) {
    std::cin >> A[i] >> B[i];
  }
  curseChanges(U, A, B);

  bool correct = true;
  for (int i=0; i<Q; i++) {
    int X,Y,V,CorrectAnswer;
    std::cin >> X >> Y >> V >> CorrectAnswer;
    int YourAnswer = question(X,Y,V);
    if (YourAnswer != CorrectAnswer) {
      std::cout << "WA! Question: " << i
		<< " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
		<<  "Your answer: " << YourAnswer
                << " Correct Answer: " << CorrectAnswer << std::endl;
      correct = false;
    } else {
      std::cerr << YourAnswer << " - OK" << std::endl;
    }
  }

  if (correct) {
    std::cout << "Correct." << std::endl;
  } else std::cout << "Incorrect." << std::endl;
  return 0;
}
/**/

Compilation message

potion.cpp:218:1: warning: "/*" within comment [-Wcomment]
  218 | /**/
      |  
potion.cpp: In member function 'void Node::toList(v&)':
potion.cpp:90:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   90 |         if (val == 0 || arr.size() >= D) return;
      |                         ~~~~~~~~~~~^~~~
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:132:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (ll j = 0; j < sometimesNeighbors[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:170:14: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:170:42: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
      |                                        ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:175:15: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |         if (j < yNeighborsArr.size() - 1) mini = min(mini, abs(iHeight - H[sometimesNeighbors[y][yNeighborsArr[j + 1]]]));
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 2 ms 1112 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 18 ms 22744 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 167328 KB Output is correct
2 Correct 517 ms 167376 KB Output is correct
3 Correct 210 ms 146644 KB Output is correct
4 Correct 1982 ms 260968 KB Output is correct
5 Correct 956 ms 222804 KB Output is correct
6 Correct 2235 ms 173008 KB Output is correct
7 Correct 667 ms 149192 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 167400 KB Output is correct
2 Correct 2534 ms 167912 KB Output is correct
3 Correct 1767 ms 164160 KB Output is correct
4 Correct 2923 ms 172996 KB Output is correct
5 Correct 611 ms 171208 KB Output is correct
6 Correct 2922 ms 173000 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8792 KB Output is correct
2 Correct 77 ms 10840 KB Output is correct
3 Correct 96 ms 7768 KB Output is correct
4 Correct 444 ms 10328 KB Output is correct
5 Correct 397 ms 9816 KB Output is correct
6 Correct 98 ms 10328 KB Output is correct
7 Correct 354 ms 8536 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 1112 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 2 ms 1112 KB Output is correct
5 Correct 18 ms 22744 KB Output is correct
6 Correct 519 ms 167328 KB Output is correct
7 Correct 517 ms 167376 KB Output is correct
8 Correct 210 ms 146644 KB Output is correct
9 Correct 1982 ms 260968 KB Output is correct
10 Correct 956 ms 222804 KB Output is correct
11 Correct 2235 ms 173008 KB Output is correct
12 Correct 667 ms 149192 KB Output is correct
13 Correct 577 ms 167400 KB Output is correct
14 Correct 2534 ms 167912 KB Output is correct
15 Correct 1767 ms 164160 KB Output is correct
16 Correct 2923 ms 172996 KB Output is correct
17 Correct 611 ms 171208 KB Output is correct
18 Correct 2922 ms 173000 KB Output is correct
19 Correct 35 ms 8792 KB Output is correct
20 Correct 77 ms 10840 KB Output is correct
21 Correct 96 ms 7768 KB Output is correct
22 Correct 444 ms 10328 KB Output is correct
23 Correct 397 ms 9816 KB Output is correct
24 Correct 98 ms 10328 KB Output is correct
25 Correct 354 ms 8536 KB Output is correct
26 Correct 972 ms 154056 KB Output is correct
27 Correct 1859 ms 163888 KB Output is correct
28 Correct 1727 ms 180644 KB Output is correct
29 Correct 2262 ms 260672 KB Output is correct
30 Execution timed out 3092 ms 173052 KB Time limit exceeded
31 Halted 0 ms 0 KB -