Submission #1121875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121875		SalihSahin	Horses (IOI15_horses)	C++14	54 / 100	1575 ms	64932 KiB

horses

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "horses.h"
 
const long long mod = 1e9 + 7;

struct SEGT{
    vector<__int128> tree;

    void init(int n){
        tree.assign(4*n, 0);
    }

    void update(int ind, int l, int r, int pos, int val){
        if(l == r){
            tree[ind] = val;
        }
        else{
            int m = (l + r)/2;

            if(pos <= m) update(ind*2, l, m, pos, val);
            else update(ind*2+1, m+1, r, pos, val);

            tree[ind] = (tree[ind*2] * tree[ind*2+1])%mod;
        }
    }

    __int128 query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql || ql > qr) return 1;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            int m = (l + r)/2;

            return (query(ind*2, l, m, ql, qr) * query(ind*2+1, m+1, r, ql, qr))%mod;
        }
    }
};
 
vector<array<__int128, 2> > arr;
int n;
SEGT seg;
 
int init(int N, int X[], int Y[]){
    arr.resize(N);
    n = N;
    seg.init(N);
    for(int i = 0; i < N; i++){
        arr[i] = {X[i], Y[i]};
        seg.update(1, 1, N, i+1, arr[i][0]);
    }
 
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; i++){
        vl *= arr[i][0];
        ans = max(ans, vl * arr[i][1]);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}
 
int updateX(int pos, int val) { 
    int N = n;
    arr[pos][0] = val;
    seg.update(1, 1, N, pos+1, val);
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; i++){
        vl *= arr[i][0];
        ans = max(ans, vl * arr[i][1]);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}
 
int updateY(int pos, int val){
    int N = n;
    arr[pos][1] = val;
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; i++){
        vl *= arr[i][0];
        ans = max(ans, vl * arr[i][1]);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:50:43: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   50 |         seg.update(1, 1, N, i+1, arr[i][0]);
      |                                           ^
horses.cpp:73:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
   73 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:101:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  101 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  128 |     int res = ans;
      |               ^~~

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