Submission #586445

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
586445	2022-06-30T09:26:00 Z	tranxuanbach	Horses (IOI15_horses)	C++17	100 / 100	355 ms	53412 KB

horses

#ifndef FEXT

#include "horses.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define int long long
// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

template<class T, class F>
struct segment_tree{
    int n, size, log;
    vector<T> data;
    F TT; // monoid operation (always adjacent)
    T T_id; // monoid identity
    // O(n)
    segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
    // O(n)
    segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
    // O(n)
    segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
        log = __lg(max(n - 1, 1)) + 1, size = 1 << log;
        data = vector<T>(size << 1, T_id);
        copy(a.begin(), a.end(), data.begin() + size);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
    }
    // O(1)
    void refresh(int i){
        data[i] = TT(data[i << 1], data[i << 1 | 1]);
    }
    // O(log n)
    void set(int p, T x){
        assert(0 <= p && p < n);
        data[p += size] = x;
        for(auto i = 1; i <= log; ++ i) refresh(p >> i);
    }
    // O(1)
    T query(int p) const{
        assert(0 <= p && p < n);
        return data[p + size];
    }
    // O(log n)
    T query(int l, int r) const{
        assert(0 <= l && l <= r && r <= n);
        T res_left = T_id, res_right = T_id;
        for(l += size, r += size; l < r; l >>= 1, r >>= 1){
            if(l & 1) res_left = TT(res_left, data[l ++]);
            if(r & 1) res_right = TT(data[-- r], res_right);
        }
        return TT(res_left, res_right);
    }
    // O(1)
    T query_all() const{
        return data[1];
    }
    // pred(sum[l, r)) is T, T, ..., T, F, F, ..., F
    // Returns max r with T
    // O(log n)
    int max_pref(int l, auto pred) const{
        assert(0 <= l && l <= n && pred(T_id));
        if(l == n) return n;
        l += size;
        T sm = T_id;
        do{
            while(~l & 1) l >>= 1;
            if(!pred(TT(sm, data[l]))){
                while(l < size){
                    l = l << 1;
                    if(pred(TT(sm, data[l]))) sm = TT(sm, data[l ++]);
                }
                return l - size;
            }
            sm = TT(sm, data[l ++]);
        }while((l & -l) != l);
        return n;
    }
    // pred(sum[l, r)) is F, F, ..., F, T, T, ..., T
    // Returns min l with T
    // O(log n)
    int min_suff(int r, auto pred) const{
        assert(0 <= r && r <= n && pred(T_id));
        if(r == 0) return 0;
        r += size;
        T sm = T_id;
        do{
            -- r;
            while(r > 1 && r & 1) r >>= 1;
            if(!pred(TT(data[r], sm))){
                while(r < size){
                    r = r << 1 | 1;
                    if(pred(TT(data[r], sm))) sm = TT(data[r --], sm);
                }
                return r + 1 - size;
            }
            sm = TT(data[r], sm);
        }while((r & -r) != r);
        return 0;
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, const segment_tree<T, F> &seg){
        out << "[";
        for(auto i = 0; i < seg.n; ++ i){
            out << seg.query(i);
            if(i != seg.n - 1) out << ", ";
        }
        return out << ']';
    }
};

const int N = 5e5 + 5, inf = 1e9 + 7, mod = 1e9 + 7;

struct Tmax{
    int mx;

    Tmax(int mx = numeric_limits <int>::min()): mx(mx){

    }
};

auto TTmax = [](const Tmax &lhs, const Tmax &rhs){
    return Tmax(max(lhs.mx, rhs.mx));
};

struct Tprod{
    int prod;

    Tprod(int prod = 1): prod(prod){

    }
};

auto TTprod = [](const Tprod &lhs, const Tprod &rhs){
    return Tprod((ll)lhs.prod * rhs.prod % mod);
};

int n;
int x[N], y[N];

set <int> stt;

segment_tree <Tprod, decltype(TTprod)> segx(N, TTprod, Tprod());
segment_tree <Tmax, decltype(TTmax)> segy(N, TTmax, Tmax());

int real_solve(){
    auto itr = prev(stt.end());
    int prod = 1;
    while (itr != stt.begin() and (ll)prod * x[(*itr)] < inf){
        prod *= x[*itr];
        itr = prev(itr);
    }

    int ans = segx.query(0, *itr + 1).prod;
    prod = 1; ll mxprod = 0;
    while (itr != stt.end()){
        int l = max(0, *itr), r = (next(itr) == stt.end() ? n : *next(itr));
        mxprod = max(mxprod, (ll)prod * segy.query(l, r).mx);
        if (next(itr) != stt.end()){
            prod *= x[*next(itr)];
        }
        itr = next(itr);
    }
    mxprod %= mod;
    ans = (ll)ans * mxprod % mod;
    return ans;
}

int init(int _n, int _x[], int _y[]){
    n = _n;
    For(i, 0, n){
        x[i] = _x[i];
        y[i] = _y[i];
    }

    stt.emplace(-1);
    For(i, 0, n){
        if (x[i] != 1){
            stt.emplace(i);
        }
    }
    For(i, 0, n){
        segx.set(i, Tprod(x[i]));
        segy.set(i, Tmax(y[i]));
    }

    return real_solve();
}

int updateX(int pos, int val){
    if (x[pos] != 1 and val == 1){
        stt.erase(pos);
    }
    if (x[pos] == 1 and val != 1){
        stt.emplace(pos);
    }
    segx.set(pos, Tprod(val));
    x[pos] = val;
    return real_solve();
}

int updateY(int pos, int val){
    segy.set(pos, Tmax(val));
    y[pos] = val;
    return real_solve();
}

#ifdef FEXT

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

signed main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    _inputFile = fopen("KEK.inp", "rb");
    _outputFile = fopen("KEK.out", "w");
    
    int N; N = _readInt();

    int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

    for (int i = 0; i < N; i++) {
        X[i] = _readInt();
    }

    for (int i = 0; i < N; i++) {
        Y[i] = _readInt();
    }   

    fprintf(_outputFile,"%d\n",init(N,X,Y));

    int M; M = _readInt();

    for (int i = 0; i < M; i++) {
        int type; type = _readInt();
        int pos; pos = _readInt();
        int val; val = _readInt(); 

        if (type == 1) {
            fprintf(_outputFile,"%d\n",updateX(pos,val));
        } else if (type == 2) {
            fprintf(_outputFile,"%d\n",updateY(pos,val));
        }
    }

    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message

horses.cpp:80:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   80 |     int max_pref(int l, auto pred) const{
      |                         ^~~~
horses.cpp:101:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  101 |     int min_suff(int r, auto pred) const{
      |                         ^~~~
horses.cpp: In constructor 'segment_tree<T, F>::segment_tree(int, F, T)':
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp: In constructor 'segment_tree<T, F>::segment_tree(int, T, F, T)':
horses.cpp:40:41: warning: declaration of 'T_id' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   40 |     segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
      |                                       ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:40:35: warning: declaration of 'TT' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   40 |     segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
      |                                 ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:40:22: warning: declaration of 'n' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   40 |     segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp: In constructor 'segment_tree<T, F>::segment_tree(const std::vector<_Tp>&, F, T)':
horses.cpp:42:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                            ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:42:40: warning: declaration of 'TT' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                      ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp: In constructor 'Tmax::Tmax(int)':
horses.cpp:136:14: warning: declaration of 'mx' shadows a member of 'Tmax' [-Wshadow]
  136 |     Tmax(int mx = numeric_limits <int>::min()): mx(mx){
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:134:9: note: shadowed declaration is here
  134 |     int mx;
      |         ^~
horses.cpp: In constructor 'Tmax::Tmax(int)':
horses.cpp:136:14: warning: declaration of 'mx' shadows a member of 'Tmax' [-Wshadow]
  136 |     Tmax(int mx = numeric_limits <int>::min()): mx(mx){
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:134:9: note: shadowed declaration is here
  134 |     int mx;
      |         ^~
horses.cpp: In constructor 'Tmax::Tmax(int)':
horses.cpp:136:14: warning: declaration of 'mx' shadows a member of 'Tmax' [-Wshadow]
  136 |     Tmax(int mx = numeric_limits <int>::min()): mx(mx){
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:134:9: note: shadowed declaration is here
  134 |     int mx;
      |         ^~
horses.cpp: In constructor 'Tprod::Tprod(int)':
horses.cpp:148:15: warning: declaration of 'prod' shadows a member of 'Tprod' [-Wshadow]
  148 |     Tprod(int prod = 1): prod(prod){
      |           ~~~~^~~~~~~~
horses.cpp:146:9: note: shadowed declaration is here
  146 |     int prod;
      |         ^~~~
horses.cpp: In constructor 'Tprod::Tprod(int)':
horses.cpp:148:15: warning: declaration of 'prod' shadows a member of 'Tprod' [-Wshadow]
  148 |     Tprod(int prod = 1): prod(prod){
      |           ~~~~^~~~~~~~
horses.cpp:146:9: note: shadowed declaration is here
  146 |     int prod;
      |         ^~~~
horses.cpp: In constructor 'Tprod::Tprod(int)':
horses.cpp:148:15: warning: declaration of 'prod' shadows a member of 'Tprod' [-Wshadow]
  148 |     Tprod(int prod = 1): prod(prod){
      |           ~~~~^~~~~~~~
horses.cpp:146:9: note: shadowed declaration is here
  146 |     int prod;
      |         ^~~~
horses.cpp: In lambda function:
horses.cpp:154:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  154 |     return Tprod((ll)lhs.prod * rhs.prod % mod);
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int real_solve()':
horses.cpp:184:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  184 |     ans = (ll)ans * mxprod % mod;
      |           ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In instantiation of 'segment_tree<T, F>::segment_tree(int, F, T) [with T = Tprod; F = <lambda(const Tprod&, const Tprod&)>]':
horses.cpp:162:63:   required from here
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp: In instantiation of 'segment_tree<T, F>::segment_tree(int, F, T) [with T = Tmax; F = <lambda(const Tmax&, const Tmax&)>]':
horses.cpp:163:59:   required from here
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp:38:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                               ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:38:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:38:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   38 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:33:9: note: shadowed declaration is here
   33 |     int n, size, log;
      |         ^
horses.cpp: In instantiation of 'segment_tree<T, F>::segment_tree(const std::vector<_Tp>&, F, T) [with T = Tprod; F = <lambda(const Tprod&, const Tprod&)>]':
horses.cpp:38:81:   required from 'segment_tree<T, F>::segment_tree(int, F, T) [with T = Tprod; F = <lambda(const Tprod&, const Tprod&)>]'
horses.cpp:162:63:   required from here
horses.cpp:42:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                            ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:42:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                      ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:42:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                            ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:42:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                      ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:42:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                            ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:42:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                      ~~^~
horses.cpp:35:7: note: shadowed declaration is here
   35 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp: In instantiation of 'segment_tree<T, F>::segment_tree(const std::vector<_Tp>&, F, T) [with T = Tmax; F = <lambda(const Tmax&, const Tmax&)>]':
horses.cpp:38:81:   required from 'segment_tree<T, F>::segment_tree(int, F, T) [with T = Tmax; F = <lambda(const Tmax&, const Tmax&)>]'
horses.cpp:163:59:   required from here
horses.cpp:42:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id){ // O(n)
      |                                            ~~^~~~
horses.cpp:36:7: note: shadowed declaration is here
   36 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:42:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   42 |     segment_tree(const vector<T> &a, F TT, T T_id): n((int)a.s

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10416 KB	Output is correct
2	Correct	8 ms	10416 KB	Output is correct
3	Correct	8 ms	10416 KB	Output is correct
4	Correct	8 ms	10416 KB	Output is correct
5	Correct	7 ms	10432 KB	Output is correct
6	Correct	8 ms	10416 KB	Output is correct
7	Correct	8 ms	10416 KB	Output is correct
8	Correct	8 ms	10416 KB	Output is correct
9	Correct	8 ms	10416 KB	Output is correct
10	Correct	8 ms	10416 KB	Output is correct
11	Correct	7 ms	10436 KB	Output is correct
12	Correct	8 ms	10416 KB	Output is correct
13	Correct	8 ms	10416 KB	Output is correct
14	Correct	12 ms	10408 KB	Output is correct
15	Correct	8 ms	10416 KB	Output is correct
16	Correct	8 ms	10416 KB	Output is correct
17	Correct	8 ms	10416 KB	Output is correct
18	Correct	8 ms	10416 KB	Output is correct
19	Correct	11 ms	10432 KB	Output is correct
20	Correct	9 ms	10416 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10416 KB	Output is correct
2	Correct	8 ms	10452 KB	Output is correct
3	Correct	8 ms	10412 KB	Output is correct
4	Correct	9 ms	10416 KB	Output is correct
5	Correct	8 ms	10416 KB	Output is correct
6	Correct	8 ms	10416 KB	Output is correct
7	Correct	9 ms	10416 KB	Output is correct
8	Correct	9 ms	10416 KB	Output is correct
9	Correct	8 ms	10416 KB	Output is correct
10	Correct	8 ms	10416 KB	Output is correct
11	Correct	8 ms	10416 KB	Output is correct
12	Correct	8 ms	10416 KB	Output is correct
13	Correct	8 ms	10416 KB	Output is correct
14	Correct	8 ms	10492 KB	Output is correct
15	Correct	8 ms	10416 KB	Output is correct
16	Correct	8 ms	10416 KB	Output is correct
17	Correct	9 ms	10416 KB	Output is correct
18	Correct	8 ms	10436 KB	Output is correct
19	Correct	8 ms	10416 KB	Output is correct
20	Correct	8 ms	10416 KB	Output is correct
21	Correct	8 ms	10416 KB	Output is correct
22	Correct	8 ms	10544 KB	Output is correct
23	Correct	9 ms	10416 KB	Output is correct
24	Correct	9 ms	10416 KB	Output is correct
25	Correct	10 ms	10440 KB	Output is correct
26	Correct	10 ms	10460 KB	Output is correct
27	Correct	10 ms	10416 KB	Output is correct
28	Correct	9 ms	10484 KB	Output is correct
29	Correct	9 ms	10488 KB	Output is correct
30	Correct	9 ms	10464 KB	Output is correct
31	Correct	9 ms	10432 KB	Output is correct
32	Correct	10 ms	10512 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	329 ms	40880 KB	Output is correct
2	Correct	319 ms	53412 KB	Output is correct
3	Correct	299 ms	44656 KB	Output is correct
4	Correct	306 ms	48432 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	10416 KB	Output is correct
2	Correct	8 ms	10416 KB	Output is correct
3	Correct	7 ms	10384 KB	Output is correct
4	Correct	8 ms	10416 KB	Output is correct
5	Correct	8 ms	10388 KB	Output is correct
6	Correct	8 ms	10416 KB	Output is correct
7	Correct	8 ms	10436 KB	Output is correct
8	Correct	8 ms	10428 KB	Output is correct
9	Correct	8 ms	10416 KB	Output is correct
10	Correct	8 ms	10416 KB	Output is correct
11	Correct	8 ms	10416 KB	Output is correct
12	Correct	8 ms	10416 KB	Output is correct
13	Correct	8 ms	10376 KB	Output is correct
14	Correct	8 ms	10416 KB	Output is correct
15	Correct	8 ms	10416 KB	Output is correct
16	Correct	8 ms	10416 KB	Output is correct
17	Correct	10 ms	10488 KB	Output is correct
18	Correct	8 ms	10388 KB	Output is correct
19	Correct	8 ms	10416 KB	Output is correct
20	Correct	10 ms	10392 KB	Output is correct
21	Correct	8 ms	10416 KB	Output is correct
22	Correct	8 ms	10496 KB	Output is correct
23	Correct	9 ms	10456 KB	Output is correct
24	Correct	9 ms	10416 KB	Output is correct
25	Correct	9 ms	10504 KB	Output is correct
26	Correct	9 ms	10508 KB	Output is correct
27	Correct	9 ms	10432 KB	Output is correct
28	Correct	8 ms	10436 KB	Output is correct
29	Correct	8 ms	10416 KB	Output is correct
30	Correct	8 ms	10504 KB	Output is correct
31	Correct	9 ms	10416 KB	Output is correct
32	Correct	9 ms	10484 KB	Output is correct
33	Correct	112 ms	20500 KB	Output is correct
34	Correct	113 ms	20460 KB	Output is correct
35	Correct	253 ms	50812 KB	Output is correct
36	Correct	261 ms	50720 KB	Output is correct
37	Correct	112 ms	18596 KB	Output is correct
38	Correct	162 ms	31404 KB	Output is correct
39	Correct	102 ms	18356 KB	Output is correct
40	Correct	237 ms	45852 KB	Output is correct
41	Correct	105 ms	18536 KB	Output is correct
42	Correct	106 ms	18488 KB	Output is correct
43	Correct	227 ms	46304 KB	Output is correct
44	Correct	230 ms	46244 KB	Output is correct

Subtask #5

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10416 KB	Output is correct
2	Correct	8 ms	10416 KB	Output is correct
3	Correct	7 ms	10416 KB	Output is correct
4	Correct	9 ms	10432 KB	Output is correct
5	Correct	8 ms	10416 KB	Output is correct
6	Correct	8 ms	10416 KB	Output is correct
7	Correct	8 ms	10416 KB	Output is correct
8	Correct	9 ms	10472 KB	Output is correct
9	Correct	8 ms	10416 KB	Output is correct
10	Correct	8 ms	10416 KB	Output is correct
11	Correct	8 ms	10416 KB	Output is correct
12	Correct	8 ms	10416 KB	Output is correct
13	Correct	8 ms	10488 KB	Output is correct
14	Correct	8 ms	10416 KB	Output is correct
15	Correct	8 ms	10416 KB	Output is correct
16	Correct	8 ms	10416 KB	Output is correct
17	Correct	9 ms	10492 KB	Output is correct
18	Correct	8 ms	10416 KB	Output is correct
19	Correct	8 ms	10380 KB	Output is correct
20	Correct	8 ms	10416 KB	Output is correct
21	Correct	7 ms	10416 KB	Output is correct
22	Correct	8 ms	10416 KB	Output is correct
23	Correct	8 ms	10416 KB	Output is correct
24	Correct	8 ms	10416 KB	Output is correct
25	Correct	9 ms	10528 KB	Output is correct
26	Correct	12 ms	10564 KB	Output is correct
27	Correct	9 ms	10416 KB	Output is correct
28	Correct	9 ms	10416 KB	Output is correct
29	Correct	10 ms	10500 KB	Output is correct
30	Correct	10 ms	10416 KB	Output is correct
31	Correct	9 ms	10416 KB	Output is correct
32	Correct	9 ms	10416 KB	Output is correct
33	Correct	355 ms	44652 KB	Output is correct
34	Correct	331 ms	53372 KB	Output is correct
35	Correct	312 ms	44580 KB	Output is correct
36	Correct	313 ms	48384 KB	Output is correct
37	Correct	112 ms	20464 KB	Output is correct
38	Correct	112 ms	20484 KB	Output is correct
39	Correct	262 ms	50736 KB	Output is correct
40	Correct	250 ms	50784 KB	Output is correct
41	Correct	111 ms	18664 KB	Output is correct
42	Correct	164 ms	31460 KB	Output is correct
43	Correct	102 ms	18456 KB	Output is correct
44	Correct	232 ms	45772 KB	Output is correct
45	Correct	108 ms	18440 KB	Output is correct
46	Correct	108 ms	18504 KB	Output is correct
47	Correct	227 ms	46252 KB	Output is correct
48	Correct	233 ms	46320 KB	Output is correct
49	Correct	160 ms	23560 KB	Output is correct
50	Correct	161 ms	23524 KB	Output is correct
51	Correct	320 ms	52732 KB	Output is correct
52	Correct	318 ms	52144 KB	Output is correct
53	Correct	233 ms	22112 KB	Output is correct
54	Correct	248 ms	35372 KB	Output is correct
55	Correct	145 ms	19456 KB	Output is correct
56	Correct	303 ms	47608 KB	Output is correct
57	Correct	163 ms	20092 KB	Output is correct
58	Correct	207 ms	20700 KB	Output is correct
59	Correct	229 ms	46144 KB	Output is correct