oj.uz

답안 #1015263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1015263 2024-07-06T08:08:07 Z 우민규(#10889) 말 (IOI15_horses) C++14
17 / 100
 1500 ms 20056 KB 
#include "horses.h"

#include <bits/stdc++.h>
using namespace std;

// bounded u32
struct bu32 {
  uint32_t inner;
  friend bu32 operator*(const bu32& lhs, const bu32& rhs) {
    uint64_t res = (uint64_t)lhs.inner * (uint64_t)rhs.inner;
    return {(uint32_t)min(res, (uint64_t)UINT32_MAX)};
  }
  friend bool operator<(const bu32& lhs, const bu32& rhs) {
    assert(lhs.inner != UINT32_MAX || rhs.inner != UINT32_MAX);
    return lhs.inner < rhs.inner;
  }
};
const int mod = 1'000'000'007;
struct modu32 {
  uint32_t inner;
  friend modu32 operator*(const modu32& lhs, const modu32& rhs) {
    return {(uint32_t)((uint64_t)lhs.inner * (uint64_t)rhs.inner % mod)};
  }
};

// range mul seg
template <typename T>
struct Seg {
  int n;
  vector<T> seg;
  Seg() {};
  Seg(int _n, int* arr) : n(_n) {
    seg.resize(2 * n);
    for (int i = 0; i < n; ++i) {
      seg[i + n] = {(uint32_t)arr[i]};
    }
    for (int i = n - 1; i > 0; --i) {
      seg[i] = seg[2 * i] * seg[2 * i + 1];
    }
  }
  void set(int i, T val) {
    i += n;
    seg[i] = val;
    while (i > 1) {
      i /= 2;
      seg[i] = seg[2 * i] * seg[2 * i + 1];
    }
  }
  T prod(int l, int r) {
    l += n, r += n;
    T naive{1};
    for (int i = l; i < r; ++i) {
      naive = naive * seg[i];
    }
    T res{1};
    while (l < r) {
      if (l & 1) {
        res = res * seg[l];
        l += 1;
      }
      if (r & 1) {
        r -= 1;
        res = res * seg[r];
      }

      l /= 2, r /= 2;
    }
    // assert(naive.inner == res.inner);
    return res;
  }
};

struct Seg2 {
  int n;
  Seg<bu32> x;
  Seg<modu32> x_prod;
  vector<int> y;
  vector<int> seg;
  int max(int i, int j) {
    if (i > j) swap(i, j);
    return (bu32){y[i]} < (bu32){y[j]} * x.prod(i + 1, j + 1) ? j : i;
  }
  Seg2() {};
  Seg2(int _n, int* _x, int* _y)
      : n(_n), x(_n, _x), x_prod(_n, _x), y(_y, _y + _n), seg(2 * _n, 0) {
    iota(seg.begin() + n, seg.begin() + 2 * n, 0);
    for (int i = n - 1; i > 0; --i) {
      seg[i] = this->max(seg[2 * i], seg[2 * i + 1]);
    }
  }
  void upd(int i) {
    while (i > 1) {
      i /= 2;
      seg[i] = this->max(seg[2 * i], seg[2 * i + 1]);
    }
  }
  void setx(int i, int val) {
    x.set(i, {(uint32_t)val});
    x_prod.set(i, {(uint32_t)val});
    upd(i + n);
  }
  void sety(int i, int val) {
    y[i] = val;
    upd(i + n);
  }
  int max() {
    int loc = seg[1];
    int cur_max_idx = 0;
    for (int i = 0; i < n; ++i) {
      cur_max_idx = this->max(cur_max_idx, i);
    }
    assert(loc == cur_max_idx);
    return (x_prod.prod(0, loc + 1) * (modu32){y[loc]}).inner;
  }
};

Seg2 GLOBAL;

int init(int n, int x[], int y[]) {
  GLOBAL = Seg2(n, x, y);
  return GLOBAL.max();
}

int updateX(int pos, int val) {
  GLOBAL.setx(pos, val);
  return GLOBAL.max();
}

int updateY(int pos, int val) {
  GLOBAL.sety(pos, val);
  return GLOBAL.max();
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message

horses.cpp: In member function 'int Seg2::max(int, int)':
horses.cpp:81:23: warning: narrowing conversion of '((Seg2*)this)->Seg2::y.std::vector<int>::operator[](((std::vector<int>::size_type)i))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'uint32_t' {aka 'unsigned int'} [-Wnarrowing]
   81 |     return (bu32){y[i]} < (bu32){y[j]} * x.prod(i + 1, j + 1) ? j : i;
      |                       ^
horses.cpp:81:38: warning: narrowing conversion of '((Seg2*)this)->Seg2::y.std::vector<int>::operator[](((std::vector<int>::size_type)j))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'uint32_t' {aka 'unsigned int'} [-Wnarrowing]
   81 |     return (bu32){y[i]} < (bu32){y[j]} * x.prod(i + 1, j + 1) ? j : i;
      |                                      ^
horses.cpp: In member function 'int Seg2::max()':
horses.cpp:113:54: warning: narrowing conversion of '((Seg2*)this)->Seg2::y.std::vector<int>::operator[](((std::vector<int>::size_type)loc))' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'uint32_t' {aka 'unsigned int'} [-Wnarrowing]
  113 |     return (x_prod.prod(0, loc + 1) * (modu32){y[loc]}).inner;
      |                                                      ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 440 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 10 ms 344 KB Output is correct
24 Correct 9 ms 348 KB Output is correct
25 Correct 5 ms 348 KB Output is correct
26 Correct 5 ms 500 KB Output is correct
27 Runtime error 4 ms 604 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1554 ms 20056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 9 ms 496 KB Output is correct
24 Correct 9 ms 348 KB Output is correct
25 Correct 5 ms 500 KB Output is correct
26 Correct 5 ms 348 KB Output is correct
27 Runtime error 4 ms 604 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 9 ms 348 KB Output is correct
24 Correct 9 ms 348 KB Output is correct
25 Correct 5 ms 344 KB Output is correct
26 Correct 5 ms 348 KB Output is correct
27 Runtime error 4 ms 484 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -