Submission #1121998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121998		SalihSahin	Horses (IOI15_horses)	C++14	0 / 100	1583 ms	135392 KiB

horses

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "horses.h"
 
const long long mod = 1e9 + 7;
 
struct SEGTWALK{
    vector<int> tree, tree2;
 
    void init(int n){
        tree.assign(4*n, 0);
        tree2.assign(4*n, 0);
    }
 
    void update(int ind, int l, int r, int pos, int val){
        if(l == r){
            tree[ind] = val;
            if(val > 1) tree2[ind] = l;
            else tree2[ind] = 1;
        }
        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] = max(tree[ind*2], tree[ind*2+1]);
            tree2[ind] = max(tree2[ind*2], tree2[ind*2+1]);
        }
    }
 
    int querymax(int ind, int l, int r, int ql, int qr){
        if(l > r || ql > qr || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            int m = (l + r)/2;
 
            return max(querymax(ind*2, l, m, ql, qr), querymax(ind*2+1, m+1, r, ql, qr));
        }
    }
 
    int queryleft(int ind, int l, int r, int ql, int qr){
        if(l > r || ql > qr || l > qr || r < ql) return 1;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            int m = (l + r)/2;
 
            return max(queryleft(ind*2, l, m, ql, qr), queryleft(ind*2+1, m+1, r, ql, qr));
        }
    }
};
 
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;
SEGTWALK segwalk;
 
int init(int N, int X[], int Y[]){
    arr.resize(N);
    n = N;
    seg.init(N);
    segwalk.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]);
        segwalk.update(1, 1, N, i+1, arr[i][1]);
    }
 
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; ;){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
        if(i > 0) i = segwalk.queryleft(1, 1, N, 1, i) - 1;
        else 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];
        __int128 nxtmax = segwalk.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);
    }
    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; ;){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
        if(i > 0) i = segwalk.queryleft(1, 1, N, 1, i) - 1;
        else 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];
        __int128 nxtmax = segwalk.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}
 
int updateY(int pos, int val){
    int N = n;
    arr[pos][1] = val;
    segwalk.update(1, 1, N, pos+1, arr[pos][1]);
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; ;){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
        if(i > 0) i = segwalk.queryleft(1, 1, N, 1, i) - 1;
        else 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];
        __int128 nxtmax = segwalk.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);
    }
    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:98:43: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   98 |         seg.update(1, 1, N, i+1, arr[i][0]);
      |                                           ^
horses.cpp:99:47: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   99 |         segwalk.update(1, 1, N, i+1, arr[i][1]);
      |                                               ^
horses.cpp:125:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  125 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:156:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  156 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:163:47: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
  163 |     segwalk.update(1, 1, N, pos+1, arr[pos][1]);
      |                                               ^
horses.cpp:187:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  187 |     int res = ans;
      |               ^~~

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