oj.uz

Submission #645938

# Submission time Handle Problem Language Result Execution time Memory
645938 2022-09-28T10:13:16 Z Pety The Potion of Great Power (CEOI20_potion) C++14
17 / 100
 359 ms 48296 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int H[200002], N, lg2[200002];

struct interval {
  int l, r, ind;
  bool operator < (const interval &other) {
    return l < other.l;
  }
};

vector<interval>v[200002];

void init (int n, int d, int h[]) {
  N = n;
  for (int i = 1; i <= n; i++)
    H[i] = h[i - 1];
}

vector<vector<int>>rmq[200002];

void curseChanges(int U, int A[], int B[]) {
  map<pair<int, int>, int>mp;
  for (int i = 0; i < U; i++) {
    A[i]++;
    B[i]++;
    if (A[i] > B[i])
      swap(A[i], B[i]);
    if (mp[{A[i], B[i]}] == 0) {
      mp[{A[i], B[i]}] = i + 1;
    }
    else {
      v[A[i]].push_back({mp[{A[i], B[i]}], i + 1, B[i]});
      v[B[i]].push_back({mp[{A[i], B[i]}], i + 1, A[i]});
      mp[{A[i], B[i]}] = 0;
    }
  }
  for (auto it : mp) {
    if (it.second) {
      v[it.first.first].push_back({it.second, U + 1, it.first.second});
      v[it.first.second].push_back({it.second, U + 1, it.first.first});
    }
  }
  for (int i = 1; i <= N; i++)
    sort(v[i].begin(), v[i].end());
  for (int i = 2; i <= U; i++)
    lg2[i] = lg2[i / 2] + 1;
  for (int i = 1; i <= N; i++) {
    int k = lg2[v[i].size()];
    rmq[i].resize(k + 1);
    for (int j = 0; j <= k; j++)
      rmq[i][j].resize(v[i].size());
    for (int j = 0; j < v[i].size(); j++)
      rmq[i][0][j] = j;
    for (int j = 1; j <= k; j++)
      for (int p = 0; p + (1 << j) - 1 < v[i].size(); p++) {
        int ind1 = rmq[i][j - 1][p];
        int ind2 = rmq[i][j - 1][p + (1 << (j - 1))];
        if (v[i][ind1].r > v[i][ind2].r)
          rmq[i][j][p] = ind1;
        else
          rmq[i][j][p] = ind2;
      }
  }
}

vector<int> ans;

int query (int shaman, int st, int dr) {
  int l = lg2[dr - st + 1];
  if (rmq[shaman][l][st] > rmq[shaman][l][dr - (1 << l) + 1])
    return rmq[shaman][l][st];
  else 
    return rmq[shaman][l][dr - (1 << l) + 1];
}

void rec(int shaman, int st, int dr, int day) {
  if (st > dr)
    return;
  int ind = query(shaman, st, dr);
  if (v[shaman][ind].r > day)
    ans.push_back(H[v[shaman][ind].ind]);
  else
    return;
  rec(shaman, st, ind - 1, day);
  rec(shaman, ind + 1, dr, day);
}

vector<int> find_list (int shaman, int day) {
  int st = 0, dr = v[shaman].size() - 1, lim = -1;
  while (st <= dr) {
    int mid = (st + dr) / 2;
    if (v[shaman][mid].l <= day) {
      lim = mid;
      st = mid + 1;
    }
    else
      dr = mid - 1;
  }
  ans.clear();
  rec(shaman, 0, lim, day);
  return ans;
}

int question (int X, int Y, int day) {
  X++;
  Y++;
  vector<int> D1 = find_list(X, day);
  vector<int> D2 = find_list(Y, day);
  sort(D1.begin(), D1.end());
  sort(D2.begin(), D2.end());
  int j = 0;
  int ans = INF;
  for (int i = 0; i < D1.size(); i++) {
    while (j < D2.size() && D2[j] < D1[i])
      j++;
    if (j < D2.size())
      ans = min(ans, D2[j] - D1[i]);
    if (j > 0)
      ans = min(ans, D1[i] - D2[j - 1]);   
  }
  return ans;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int j = 0; j < v[i].size(); j++)
      |                     ~~^~~~~~~~~~~~~
potion.cpp:62:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |       for (int p = 0; p + (1 << j) - 1 < v[i].size(); p++) {
      |                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for (int i = 0; i < D1.size(); i++) {
      |                   ~~^~~~~~~~~~~
potion.cpp:121:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     while (j < D2.size() && D2[j] < D1[i])
      |            ~~^~~~~~~~~~~
potion.cpp:123:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     if (j < D2.size())
      |         ~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9936 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 23 ms 13796 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 48256 KB Output is correct
2 Correct 318 ms 48228 KB Output is correct
3 Correct 178 ms 27160 KB Output is correct
4 Incorrect 236 ms 37748 KB Incorrect
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 48296 KB Output is correct
2 Incorrect 183 ms 30796 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11936 KB Output is correct
2 Incorrect 13 ms 11048 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 6 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 7 ms 9936 KB Output is correct
5 Correct 23 ms 13796 KB Output is correct
6 Correct 359 ms 48256 KB Output is correct
7 Correct 318 ms 48228 KB Output is correct
8 Correct 178 ms 27160 KB Output is correct
9 Incorrect 236 ms 37748 KB Incorrect
10 Halted 0 ms 0 KB -