Submission #426798

#	Time	Username	Problem	Language	Result	Execution time	Memory
426798		ollel	Horses (IOI15_horses)	C++17	17 / 100	135 ms	44108 KiB

horses

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define lso(x) x&(-x)

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;

struct SegTree {
  int n;
  vi tr, lazy;

  SegTree() {n = 0;}

  void INTI(int N) {n = N; tr.assign(3*n,0); lazy.assign(3*n,0);}

  int l(int i) {return i<<1;}
  int r(int i) {return (i<<1)|1;}

  ll combine(int a, int b) {return max(a, b);}

  // void propagate_mult(int x, int L, int R) {
  //   if (lazy[x] == 0) return;
  //   if (R == L) {
  //     tr[x] /= oldmaxx[x];
  //     oldmaxx[x] = lazy[x];
  //     tr[x] *= lazy[x];
  //     return;
  //   }
  //   tr[x] /= oldmaxx[x];
  //   oldmaxx[x] = lazy[x];
  //   tr[x] *= lazy[x];
  //   lazy[l(x)] = lazy[r(x)] = lazy[x];
  //   lazy[x] = 0;
  // }

  void mult(int x, int L, int R, int i, int ov, int nv) {
    if (i > R || i < L) return;

    if (R == L) {
      tr[x] /= ov;
      tr[x] *= nv;
      return;
    }

    int mid = (L + R) / 2;
    mult(l(x), L, mid, i, ov, nv);
    mult(r(x), mid + 1, R, i, ov, nv);
    tr[x] = combine(tr[l(x)], tr[r(x)]);
  }

  void mult(int i, int nv, int ov) {
    mult(1, 0, n - 1, i, nv, ov);
  }

  void assign(int x, int L, int R, int i, int v) {
    if (i < L ||i > R) return;
    if (L == R) {
      tr[x] = v;
      return;
    }
    int mid = (L + R) / 2;
    assign(l(x), L, mid, i, v);
    assign(r(x), mid + 1, R, i, v);
    tr[x] = combine(tr[l(x)], tr[r(x)]);
  }

  void assign(int i, int v) {
    assign(1, 0, n - 1, i, v);
  }

  ll query(int x, int L, int R, int i, int j) {
    if (i > R || j < L) return 0;
    if (L >= i && R <= j) return tr[x];
    int mid = (L + R) / 2;
    return combine(
      query(l(x), L, mid, i, j),
      query(r(x), mid + 1, R, i, j)
    );
  }

  ll query(int i, int j) {
    return query(1, 0, n - 1, i, j);
  }
};

vi X, Y, T;
int N;
SegTree st;

int init(int a, int x[], int y[]) {
  N = a;
  X.resize(N); Y.resize(N); T.resize(N);
  rep(i,0,N) X[i] = x[i];
  rep(i,0,N) Y[i] = y[i];
  rep(i,0,N) T[i] = X[i];
  rep(i,1,N) T[i] = T[i] * T[i - 1];

  st.INTI(N);
  rep(i,0,N) st.assign(i, T[i] * Y[i]);
  return st.query(0, N - 1) % 1000000009;
}

int updateX(int pos, int val) {
  int ov = X[pos], nv = val;
  X[pos] = nv;
  rep(i,pos,N) st.mult(i, ov, nv);
  rep(i,pos,N) {
    if (i == 0) T[i] = X[i];
    else T[i] = T[i - 1] * X[i];
  }
  return st.query(0, N - 1) % 1000000009;
}

int updateY(int pos, int val) {
  int ov = Y[pos], nv = val;
  Y[pos] = nv;
  st.assign(pos, Y[pos]*T[pos]);
  return st.query(0, N - 1) % 1000000009;
}

Compilation message (stderr)

horses.cpp: In member function 'void SegTree::mult(int, int, int, int, int, int)':
horses.cpp:53:39: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   53 |     tr[x] = combine(tr[l(x)], tr[r(x)]);
      |                                       ^
horses.cpp:53:39: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
horses.cpp: In member function 'void SegTree::assign(int, int, int, int, int)':
horses.cpp:69:39: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |     tr[x] = combine(tr[l(x)], tr[r(x)]);
      |                                       ^
horses.cpp:69:39: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
horses.cpp: In member function 'll SegTree::query(int, int, int, int, int)':
horses.cpp:81:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |       query(l(x), L, mid, i, j),
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~
horses.cpp:82:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   82 |       query(r(x), mid + 1, R, i, j)
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:104:32: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |   rep(i,0,N) st.assign(i, T[i] * Y[i]);
horses.cpp:105:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |   return st.query(0, N - 1) % 1000000009;
      |          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:109:17: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  109 |   int ov = X[pos], nv = val;
      |                 ^
horses.cpp:116:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |   return st.query(0, N - 1) % 1000000009;
      |          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:120:17: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |   int ov = Y[pos], nv = val;
      |                 ^
horses.cpp:122:24: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |   st.assign(pos, Y[pos]*T[pos]);
horses.cpp:123:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |   return st.query(0, N - 1) % 1000000009;
      |          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
horses.cpp:120:7: warning: unused variable 'ov' [-Wunused-variable]
  120 |   int ov = Y[pos], nv = val;
      |       ^~

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