oj.uz

답안 #1002508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002508 2024-06-19T15:38:24 Z yoav_s The Potion of Great Power (CEOI20_potion) C++17
52 / 100
 3000 ms 260916 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

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 23 ms 22716 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 555 ms 167236 KB Output is correct
2 Correct 521 ms 167500 KB Output is correct
3 Correct 226 ms 146600 KB Output is correct
4 Correct 1843 ms 260916 KB Output is correct
5 Correct 993 ms 222660 KB Output is correct
6 Correct 2139 ms 173040 KB Output is correct
7 Correct 694 ms 149364 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 503 ms 167620 KB Output is correct
2 Correct 2586 ms 167816 KB Output is correct
3 Correct 1802 ms 164040 KB Output is correct
4 Execution timed out 3037 ms 172804 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 8792 KB Output is correct
2 Correct 96 ms 10836 KB Output is correct
3 Correct 103 ms 7768 KB Output is correct
4 Correct 499 ms 10320 KB Output is correct
5 Correct 399 ms 9816 KB Output is correct
6 Correct 90 ms 10328 KB Output is correct
7 Correct 387 ms 8564 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 3 ms 1112 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 2 ms 1112 KB Output is correct
5 Correct 23 ms 22716 KB Output is correct
6 Correct 555 ms 167236 KB Output is correct
7 Correct 521 ms 167500 KB Output is correct
8 Correct 226 ms 146600 KB Output is correct
9 Correct 1843 ms 260916 KB Output is correct
10 Correct 993 ms 222660 KB Output is correct
11 Correct 2139 ms 173040 KB Output is correct
12 Correct 694 ms 149364 KB Output is correct
13 Correct 503 ms 167620 KB Output is correct
14 Correct 2586 ms 167816 KB Output is correct
15 Correct 1802 ms 164040 KB Output is correct
16 Execution timed out 3037 ms 172804 KB Time limit exceeded
17 Halted 0 ms 0 KB -