제출 #1185813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185813		Gabp	말 (IOI15_horses)	C++20	100 / 100	112 ms	67956 KiB

horses

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

const long long int MOD = 1e9 + 7;
const long long int INF = 2e9;
int n;

struct SegTree {
  vector<long long int> x,y,left,right,mult;
  vector<int> idx;
  
  SegTree() {}
  
  SegTree(int n, int X[], int Y[]) {
    x.resize(n);
    y.resize(n);
    left.resize(4 * n);
    right.resize(4 * n);
    mult.resize(4 * n);
    idx.resize(4 * n);
    
    for (int i = 0; i < n; i++) {
      x[i] = X[i];
      y[i] = Y[i];
    }
    
    build(1, 0, n - 1);
  }
  
  void merge(int v) {
    mult[v] = mult[2 * v] * mult[2 * v + 1] % MOD;
    
    long long int check = min(INF, right[2 * v] * left[2 * v + 1]);
    if (y[idx[2 * v]] >= y[idx[2 * v + 1]] * check) {
      idx[v] = idx[2 * v];
      left[v] = left[2 * v];
      right[v] = min(INF, min(INF, right[2 * v] * left[2 * v + 1]) * right[2 * v + 1]);
    } else {
      idx[v] = idx[2 * v + 1];
      left[v] = min(INF, min(INF, left[2 * v] * right[2 * v]) * left[2 * v + 1]);
      right[v] = right[2 * v + 1];
    }
  }
  
  void build(int v, int tl, int tr) {
    if (tl == tr) {
      left[v] = x[tl];
      idx[v] = tl;
      mult[v] = x[tl];
      right[v] = 1;
      return;
    }
    
    int mid = tl + (tr - tl) / 2;
    build(2 * v, tl, mid);
    build(2 * v + 1, mid + 1, tr);
    merge(v);
  }
  
  void update(int v, int tl, int tr, int id) {
    if (tl == tr) {
      left[v] = x[tl];
      idx[v] = tl;
      mult[v] = x[tl];
      right[v] = 1;
      return;
    }
    
    int mid = tl + (tr - tl) / 2;
    if (id <= mid) update(2 * v, tl, mid, id);
    else update(2 * v + 1, mid + 1, tr, id);
    merge(v);
  }
  
  long long int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 1;
    if (tl == l && tr == r) return mult[v];
    
    int mid = tl + (tr - tl) / 2;
    return (query(2 * v, tl, mid, l, min(mid, r)) * query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r)) % MOD;
  }
  
  long long int getAns() {
    return query(1, 0, n - 1, 0, idx[1]) * y[idx[1]] % MOD;
  }
};

SegTree st;

int init(int N, int X[], int Y[]) {
  n = N;
  st = SegTree(N, X, Y);
  return st.getAns();
}

int updateX(int pos, int val) {
  st.x[pos] = val;
  st.update(1, 0, n - 1, pos);
  return st.getAns();
}

int updateY(int pos, int val) {
  st.y[pos] = val;
  st.update(1, 0, n - 1, pos);
  return st.getAns();
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23