oj.uz

Submission #1002510

# Submission time Handle Problem Language Result Execution time Memory
1002510 2024-06-19T15:39:48 Z yoav_s The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 261096 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

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;
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) return;
        if (left == right)
        {
            arr.pb(left);
            return;
        }
        l->toList(arr);
        r->toList(arr);
    }
};

ll N;
ll D;
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:217:1: warning: "/*" within comment [-Wcomment]
  217 | /**/
      |  
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:131:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for (ll j = 0; j < sometimesNeighbors[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:169:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:169:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     while (i < xNeighborsArr.size() && j < yNeighborsArr.size())
      |                                        ~~^~~~~~~~~~~~~~~~~~~~~~
potion.cpp:174:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         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 3 ms 1112 KB Output is correct
4 Correct 26 ms 22656 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 167388 KB Output is correct
2 Correct 553 ms 167356 KB Output is correct
3 Correct 203 ms 146632 KB Output is correct
4 Correct 1718 ms 261096 KB Output is correct
5 Correct 913 ms 222652 KB Output is correct
6 Correct 1960 ms 172996 KB Output is correct
7 Correct 671 ms 149176 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 167496 KB Output is correct
2 Correct 2475 ms 167740 KB Output is correct
3 Correct 1790 ms 164112 KB Output is correct
4 Correct 2999 ms 172996 KB Output is correct
5 Correct 634 ms 171204 KB Output is correct
6 Correct 2979 ms 173000 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8556 KB Output is correct
2 Correct 82 ms 10840 KB Output is correct
3 Correct 103 ms 7768 KB Output is correct
4 Correct 476 ms 10328 KB Output is correct
5 Correct 417 ms 9816 KB Output is correct
6 Correct 88 ms 10328 KB Output is correct
7 Correct 383 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 3 ms 1112 KB Output is correct
5 Correct 26 ms 22656 KB Output is correct
6 Correct 660 ms 167388 KB Output is correct
7 Correct 553 ms 167356 KB Output is correct
8 Correct 203 ms 146632 KB Output is correct
9 Correct 1718 ms 261096 KB Output is correct
10 Correct 913 ms 222652 KB Output is correct
11 Correct 1960 ms 172996 KB Output is correct
12 Correct 671 ms 149176 KB Output is correct
13 Correct 528 ms 167496 KB Output is correct
14 Correct 2475 ms 167740 KB Output is correct
15 Correct 1790 ms 164112 KB Output is correct
16 Correct 2999 ms 172996 KB Output is correct
17 Correct 634 ms 171204 KB Output is correct
18 Correct 2979 ms 173000 KB Output is correct
19 Correct 37 ms 8556 KB Output is correct
20 Correct 82 ms 10840 KB Output is correct
21 Correct 103 ms 7768 KB Output is correct
22 Correct 476 ms 10328 KB Output is correct
23 Correct 417 ms 9816 KB Output is correct
24 Correct 88 ms 10328 KB Output is correct
25 Correct 383 ms 8536 KB Output is correct
26 Correct 945 ms 153956 KB Output is correct
27 Correct 1799 ms 164040 KB Output is correct
28 Correct 1654 ms 180680 KB Output is correct
29 Correct 2080 ms 260708 KB Output is correct
30 Execution timed out 3020 ms 173000 KB Time limit exceeded
31 Halted 0 ms 0 KB -