Submission #102703

#	Time	Username	Problem	Language	Result	Execution time	Memory
102703		wxh010910	Horses (IOI15_horses)	C++17	100 / 100	216 ms	45508 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

const int md = (int) 1e9 + 7;
const long long inf = 1ll << 30;

inline int mul(int x, int y) {
  return (int) ((long long) x * y % md);
}

class node {
 public:
  int all;
  int left;
  int right;
  int sell;
  int prod;
  int ans;
};

vector<node> tree;
vector<int> a, b;
int n;

void pull(int x, int z) {
  tree[x].all = min((long long) tree[x + 1].all * tree[z].all, inf);
  tree[x].prod = mul(tree[x + 1].prod, tree[z].prod);
  if (tree[x + 1].sell > (long long) tree[x + 1].right * tree[z].left) {
    tree[x].ans = tree[x + 1].ans;
    tree[x].sell = tree[x + 1].sell;
    tree[x].left = tree[x + 1].left;
    tree[x].right = min((long long) tree[x + 1].right * tree[z].all, inf);
  } else {
    tree[x].ans = mul(tree[z].ans, tree[x + 1].prod);
    tree[x].sell = tree[z].sell;
    tree[x].left = min((long long) tree[x + 1].all * tree[z].left, inf);
    tree[x].right = tree[z].right;
  }
}

void build(int x, int l, int r) {
  if (l == r) {
    tree[x].all = a[l];
    tree[x].prod = a[l];
    tree[x].ans = mul(a[l], b[l]);
    tree[x].sell = b[l];
    tree[x].left = min((long long) a[l] * b[l], inf);
    tree[x].right = 1;
  } else {
    int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
}

void modify(int x, int l, int r, int p) {
  if (l == r) {
    tree[x].all = a[l];
    tree[x].prod = a[l];
    tree[x].ans = mul(a[l], b[l]);
    tree[x].sell = b[l];
    tree[x].left = min((long long) a[l] * b[l], inf);
    tree[x].right = 1;
  } else {
    int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
    if (p <= y) {
      modify(x + 1, l, y, p);
    } else {
      modify(z, y + 1, r, p);
    }
    pull(x, z);
  }
}

int init(int N, int X[], int Y[]) {
  n = N;
  for (int i = 0; i < n; ++i) {
    a.push_back(X[i]);
    b.push_back(Y[i]);
  }
  tree.resize(n * 2 - 1);
  build(0, 0, n - 1);
  return tree[0].ans;
}

int updateX(int pos, int val) {
  a[pos] = val;
  modify(0, 0, n - 1, pos);
  return tree[0].ans;
}

int updateY(int pos, int val) {
  b[pos] = val;
  modify(0, 0, n - 1, pos);
  return tree[0].ans;
}

Compilation message (stderr)

horses.cpp: In function 'void pull(int, int)':
horses.cpp:28:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   tree[x].all = min((long long) tree[x + 1].all * tree[z].all, inf);
                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:34:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     tree[x].right = min((long long) tree[x + 1].right * tree[z].all, inf);
                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:38:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     tree[x].left = min((long long) tree[x + 1].all * tree[z].left, inf);
                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:49:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     tree[x].left = min((long long) a[l] * b[l], inf);
                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void modify(int, int, int, int)':
horses.cpp:65:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     tree[x].left = min((long long) a[l] * b[l], inf);
                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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