Submission #1122040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122040		SalihSahin	Horses (IOI15_horses)	C++14	100 / 100	971 ms	88340 KiB

horses

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "horses.h"
 
const long long mod = 1e9 + 7;
 
struct SEGTY{
    vector<int> 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] = max(tree[ind*2], tree[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));
        }
    }

};
 
struct SEGT{
    vector<__int128> tree;
    vector<int> tree2, tree3;
 
    void init(int n){
        tree.assign(4*n, 0);
        tree2.assign(4*n, 0);
        tree3.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] = 0;

            if(val > 1) tree3[ind] = l;
            else tree3[ind] = tree3.size()/4+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] = (tree[ind*2] * tree[ind*2+1])%mod;
            tree2[ind] = max(tree2[ind*2], tree2[ind*2+1]);
            tree3[ind] = min(tree3[ind*2], tree3[ind*2+1]);
        }
    }
 
    __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;
        }
    }

    int queryL(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 tree2[ind];
        else{
            int m = (l + r)/2;
 
            return max(queryL(ind*2, l, m, ql, qr), queryL(ind*2+1, m+1, r, ql, qr));
        }
    }

    int queryR(int ind, int l, int r, int ql, int qr){
        if(l > r || ql > qr || l > qr || r < ql) return tree3.size()/4+1;
        if(l >= ql && r <= qr) return tree3[ind];
        else{
            int m = (l + r)/2;
 
            return min(queryR(ind*2, l, m, ql, qr), queryR(ind*2+1, m+1, r, ql, qr));
        }
    }
};
 
vector<array<__int128, 2> > arr;
int n;
SEGT seg;
SEGTY segy;
 
int init(int N, int X[], int Y[]){
    arr.resize(N);
    n = N;
    seg.init(N);
    segy.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]);
        segy.update(1, 1, N, i+1, arr[i][1]);
    }
 
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
        if(i) i = seg.queryL(1, 1, N, 1, i);
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; ){
        vl *= arr[i][0];
        __int128 nxtmax = segy.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);

        i = seg.queryR(1, 1, N, i+2, N) - 1;
        if(i >= N) break;
    }
    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;
        }
        if(i) i = seg.queryL(1, 1, N, 1, i);
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; ){
        vl *= arr[i][0];
        __int128 nxtmax = segy.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);

        i = seg.queryR(1, 1, N, i+2, N) - 1;
        if(i >= N) break;
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}
 
int updateY(int pos, int val){
    int N = n;
    arr[pos][1] = val;
    segy.update(1, 1, N, pos+1, arr[pos][1]);
    __int128 vl = 1;
    int ind = 0;
    for(int i = N-1; i >= 0; i--){
        vl *= arr[i][0];
        if(vl > mod){
            ind = i;
            break;
        }
        if(i) i = seg.queryL(1, 1, N, 1, i);
    }
 
    vl = 1;
    __int128 precarp = seg.query(1, 1, N, 1, ind);
    __int128 ans = 0;
    for(int i = ind; i < N; ){
        vl *= arr[i][0];
        __int128 nxtmax = segy.querymax(1, 1, N, i + 1, N);
        ans = max(ans, vl * nxtmax);

        i = seg.queryR(1, 1, N, i+2, N) - 1;
        if(i >= N) break;
    }
    ans %= mod;
    ans *= precarp;
    ans %= mod;
    int res = ans;
    return res;
}

Compilation message (stderr)

horses.cpp: In member function 'void SEGT::update(int, int, int, int, int)':
horses.cpp:58:45: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   58 |             else tree3[ind] = tree3.size()/4+1;
      |                               ~~~~~~~~~~~~~~^~
horses.cpp: In member function 'int SEGT::queryR(int, int, int, int, int)':
horses.cpp:93:71: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   93 |         if(l > r || ql > qr || l > qr || r < ql) return tree3.size()/4+1;
      |                                                         ~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:115:43: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
  115 |         seg.update(1, 1, N, i+1, arr[i][0]);
      |                                           ^
horses.cpp:116:44: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
  116 |         segy.update(1, 1, N, i+1, arr[i][1]);
      |                                            ^
horses.cpp:144:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  144 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:177:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  177 |     int res = ans;
      |               ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:184:44: warning: conversion from 'std::array<__int128, 2>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
  184 |     segy.update(1, 1, N, pos+1, arr[pos][1]);
      |                                            ^
horses.cpp:210:15: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  210 |     int res = ans;
      |               ^~~

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