Submission #735798

#	Time	Username	Problem	Language	Result	Execution time	Memory
735798		snowman	Horses (IOI15_horses)	C++17	0 / 100	70 ms	45820 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
// #define Y cout << "YES" << '\n'
// #define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}

const ll mxa = 500005;
// string __fname = "exclusiv";  
// ifstream in(__fname + ".in"); 
// ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out 

struct cell{
    double lsum, blsum;
    ll prod, bprod;
};


int n;
ll x[mxa], y[mxa];
cell st[4 * mxa];


void combine(int v, int l, int r){
    st[v].lsum = st[l].lsum + st[r].lsum;
    st[v].prod = (st[l].prod + st[r].prod) % mod;
    if(st[l].blsum > st[l].lsum + st[r].blsum){
        st[v].blsum = st[l].blsum;
        st[v].bprod = st[l].bprod;
    }
    else{
        st[v].blsum = st[l].lsum + st[r].blsum;
        st[v].bprod = (st[l].prod * st[r].bprod) % mod;
    }
}

void build(int v, int tl, int tr){
    if(tl == tr){
        st[v].lsum = log2(x[tl]);
        st[v].prod = x[tl];
        st[v].blsum = st[v].lsum + log2(y[tl]);
        st[v].bprod = (st[v].prod * y[tl]) % mod;
    }
    else{
        int mid = (tl + tr) / 2;
        build(v*2, tl, mid);
        build(v * 2 + 1, mid + 1, tr);
        combine(v, v * 2, v * 2 + 1);
    }
}

void update(int v, int tl, int tr, int poz){
    if(tl == tr && tl == poz){
        st[v].lsum = log2(x[tl]);
        st[v].prod = x[tl];
        st[v].blsum = st[v].lsum + log2(y[tl]);
        st[v].bprod = (st[v].prod * y[tl]) % mod;
    }
    else{
        int mid = (tl  + tr) / 2;
        if(poz <= mid){
            update(v * 2, tl, mid, poz);
        }
        else{
            update(v * 2 + 1, mid + 1, tr, poz);
        }
        combine(v, v * 2, v * 2 + 1);
    }
}


int init(int N, int X[], int Y[]) {
    n = N;
    fri(0, n){
        x[i] = X[i];
        y[i] = Y[i];
    }
    build(1, 0, n - 1);
	return st[1].bprod;
}

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

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

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:109:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |  return st[1].bprod;
      |               ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |     return st[1].bprod;
      |                  ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:121:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |     return st[1].bprod;
      |                  ^

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