oj.uz

Submission #1002517

# Submission time Handle Problem Language Result Execution time Memory
1002517 2024-06-19T15:44:20 Z yoav_s The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 261308 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;
    bool 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, bool 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 || 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 constructor 'Node::Node()':
potion.cpp:40:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   40 |         val = left = right = 0;
      |               ~~~~~^~~~~~~~~~~
potion.cpp: In member function 'void Node::toList(v&)':
potion.cpp:90:32: 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 || 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 1 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 21 ms 22744 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 167276 KB Output is correct
2 Correct 520 ms 167640 KB Output is correct
3 Correct 232 ms 146636 KB Output is correct
4 Correct 2009 ms 261308 KB Output is correct
5 Correct 952 ms 222724 KB Output is correct
6 Correct 2063 ms 172824 KB Output is correct
7 Correct 620 ms 149392 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 167464 KB Output is correct
2 Correct 2484 ms 167868 KB Output is correct
3 Correct 1713 ms 163976 KB Output is correct
4 Correct 2931 ms 172864 KB Output is correct
5 Correct 652 ms 171224 KB Output is correct
6 Correct 2988 ms 172848 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8792 KB Output is correct
2 Correct 80 ms 10840 KB Output is correct
3 Correct 105 ms 7896 KB Output is correct
4 Correct 494 ms 10328 KB Output is correct
5 Correct 419 ms 10068 KB Output is correct
6 Correct 95 ms 10328 KB Output is correct
7 Correct 359 ms 8536 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 21 ms 22744 KB Output is correct
6 Correct 552 ms 167276 KB Output is correct
7 Correct 520 ms 167640 KB Output is correct
8 Correct 232 ms 146636 KB Output is correct
9 Correct 2009 ms 261308 KB Output is correct
10 Correct 952 ms 222724 KB Output is correct
11 Correct 2063 ms 172824 KB Output is correct
12 Correct 620 ms 149392 KB Output is correct
13 Correct 524 ms 167464 KB Output is correct
14 Correct 2484 ms 167868 KB Output is correct
15 Correct 1713 ms 163976 KB Output is correct
16 Correct 2931 ms 172864 KB Output is correct
17 Correct 652 ms 171224 KB Output is correct
18 Correct 2988 ms 172848 KB Output is correct
19 Correct 36 ms 8792 KB Output is correct
20 Correct 80 ms 10840 KB Output is correct
21 Correct 105 ms 7896 KB Output is correct
22 Correct 494 ms 10328 KB Output is correct
23 Correct 419 ms 10068 KB Output is correct
24 Correct 95 ms 10328 KB Output is correct
25 Correct 359 ms 8536 KB Output is correct
26 Correct 951 ms 153872 KB Output is correct
27 Correct 1920 ms 164068 KB Output is correct
28 Correct 1777 ms 180776 KB Output is correct
29 Correct 2296 ms 260632 KB Output is correct
30 Execution timed out 3072 ms 173000 KB Time limit exceeded
31 Halted 0 ms 0 KB -