oj.uz

Submission #1002513

# Submission time Handle Problem Language Result Execution time Memory
1002513 2024-06-19T15:41:44 Z yoav_s The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 261064 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;
    ll 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, ll 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);
    ll 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: 'll' {aka '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: 'll' {aka '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: 'll' {aka '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 22560 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 167368 KB Output is correct
2 Correct 526 ms 167404 KB Output is correct
3 Correct 248 ms 146764 KB Output is correct
4 Correct 1922 ms 261064 KB Output is correct
5 Correct 929 ms 222700 KB Output is correct
6 Correct 2166 ms 173016 KB Output is correct
7 Correct 686 ms 149400 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 167568 KB Output is correct
2 Correct 2561 ms 167936 KB Output is correct
3 Correct 1814 ms 164084 KB Output is correct
4 Correct 2883 ms 173008 KB Output is correct
5 Correct 619 ms 171172 KB Output is correct
6 Correct 2887 ms 173016 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8792 KB Output is correct
2 Correct 90 ms 10840 KB Output is correct
3 Correct 100 ms 7768 KB Output is correct
4 Correct 463 ms 10328 KB Output is correct
5 Correct 391 ms 9816 KB Output is correct
6 Correct 86 ms 10328 KB Output is correct
7 Correct 373 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 22560 KB Output is correct
6 Correct 510 ms 167368 KB Output is correct
7 Correct 526 ms 167404 KB Output is correct
8 Correct 248 ms 146764 KB Output is correct
9 Correct 1922 ms 261064 KB Output is correct
10 Correct 929 ms 222700 KB Output is correct
11 Correct 2166 ms 173016 KB Output is correct
12 Correct 686 ms 149400 KB Output is correct
13 Correct 542 ms 167568 KB Output is correct
14 Correct 2561 ms 167936 KB Output is correct
15 Correct 1814 ms 164084 KB Output is correct
16 Correct 2883 ms 173008 KB Output is correct
17 Correct 619 ms 171172 KB Output is correct
18 Correct 2887 ms 173016 KB Output is correct
19 Correct 33 ms 8792 KB Output is correct
20 Correct 90 ms 10840 KB Output is correct
21 Correct 100 ms 7768 KB Output is correct
22 Correct 463 ms 10328 KB Output is correct
23 Correct 391 ms 9816 KB Output is correct
24 Correct 86 ms 10328 KB Output is correct
25 Correct 373 ms 8536 KB Output is correct
26 Correct 995 ms 153912 KB Output is correct
27 Correct 1880 ms 164020 KB Output is correct
28 Correct 1723 ms 180752 KB Output is correct
29 Correct 2321 ms 260624 KB Output is correct
30 Execution timed out 3058 ms 172924 KB Time limit exceeded
31 Halted 0 ms 0 KB -