Submission #586442

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
586442	2022-06-30T09:21:03 Z	tranxuanbach	Horses (IOI15_horses)	C++17	17 / 100	311 ms	44652 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 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 * (*itr) < inf){
        prod *= *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:79:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   79 |     int max_pref(int l, auto pred) const{
      |                         ^~~~
horses.cpp:100:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  100 |     int min_suff(int r, auto pred) const{
      |                         ^~~~
horses.cpp: In constructor 'segment_tree<T, F>::segment_tree(int, F, T)':
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     int n, size, log;
      |         ^
horses.cpp: In constructor 'segment_tree<T, F>::segment_tree(int, T, F, T)':
horses.cpp:39:41: warning: declaration of 'T_id' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   39 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:39:35: warning: declaration of 'TT' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   39 |     segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
      |                                 ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:39:22: warning: declaration of 'n' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   39 |     segment_tree(int n, T init, F TT, T T_id): segment_tree(vector<T>(n, init), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     int n, size, log;
      |         ^
horses.cpp: In constructor 'segment_tree<T, F>::segment_tree(const std::vector<_Tp>&, F, T)':
horses.cpp:41:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   41 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:41:40: warning: declaration of 'TT' shadows a member of 'segment_tree<T, F>' [-Wshadow]
   41 |     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:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp: In constructor 'Tmax::Tmax(int)':
horses.cpp:135:14: warning: declaration of 'mx' shadows a member of 'Tmax' [-Wshadow]
  135 |     Tmax(int mx = numeric_limits <int>::min()): mx(mx){
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:133:9: note: shadowed declaration is here
  133 |     int mx;
      |         ^~
horses.cpp: In constructor 'Tmax::Tmax(int)':
horses.cpp:135:14: warning: declaration of 'mx' shadows a member of 'Tmax' [-Wshadow]
  135 |     Tmax(int mx = numeric_limits <int>::min()): mx(mx){
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:133:9: note: shadowed declaration is here
  133 |     int mx;
      |         ^~
horses.cpp: In constructor 'Tmax::Tmax(int)':
horses.cpp:135:14: warning: declaration of 'mx' shadows a member of 'Tmax' [-Wshadow]
  135 |     Tmax(int mx = numeric_limits <int>::min()): mx(mx){
      |          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:133:9: note: shadowed declaration is here
  133 |     int mx;
      |         ^~
horses.cpp: In constructor 'Tprod::Tprod(int)':
horses.cpp:147:15: warning: declaration of 'prod' shadows a member of 'Tprod' [-Wshadow]
  147 |     Tprod(int prod = 1): prod(prod){
      |           ~~~~^~~~~~~~
horses.cpp:145:9: note: shadowed declaration is here
  145 |     int prod;
      |         ^~~~
horses.cpp: In constructor 'Tprod::Tprod(int)':
horses.cpp:147:15: warning: declaration of 'prod' shadows a member of 'Tprod' [-Wshadow]
  147 |     Tprod(int prod = 1): prod(prod){
      |           ~~~~^~~~~~~~
horses.cpp:145:9: note: shadowed declaration is here
  145 |     int prod;
      |         ^~~~
horses.cpp: In constructor 'Tprod::Tprod(int)':
horses.cpp:147:15: warning: declaration of 'prod' shadows a member of 'Tprod' [-Wshadow]
  147 |     Tprod(int prod = 1): prod(prod){
      |           ~~~~^~~~~~~~
horses.cpp:145:9: note: shadowed declaration is here
  145 |     int prod;
      |         ^~~~
horses.cpp: In lambda function:
horses.cpp:153:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  153 |     return Tprod((ll)lhs.prod * rhs.prod % mod);
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int real_solve()':
horses.cpp:183:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  183 |     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:161:63:   required from here
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     int n, size, log;
      |         ^
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     int n, size, log;
      |         ^
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     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:162:59:   required from here
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     int n, size, log;
      |         ^
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     int n, size, log;
      |         ^
horses.cpp:37:33: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:37:27: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                         ~~^~
horses.cpp:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:37:22: warning: declaration of 'n' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   37 |     segment_tree(int n, F TT, T T_id): segment_tree(vector<T>(n, T_id), TT, T_id){}
      |                  ~~~~^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     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:37:81:   required from 'segment_tree<T, F>::segment_tree(int, F, T) [with T = Tprod; F = <lambda(const Tprod&, const Tprod&)>]'
horses.cpp:161:63:   required from here
horses.cpp:41:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   41 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:41:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   41 |     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:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:41:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   41 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:41:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   41 |     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:34:7: note: shadowed declaration is here
   34 |     F TT; // monoid operation (always adjacent)
      |       ^~
horses.cpp:41:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   41 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:41:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tprod, <lambda(const Tprod&, const Tprod&)> >' [-Wshadow]
   41 |     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:34:7: note: shadowed declaration is here
   34 |     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:37:81:   required from 'segment_tree<T, F>::segment_tree(int, F, T) [with T = Tmax; F = <lambda(const Tmax&, const Tmax&)>]'
horses.cpp:162:59:   required from here
horses.cpp:41:46: warning: declaration of 'T_id' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   41 |     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 |     T T_id; // monoid identity
      |       ^~~~
horses.cpp:41:40: warning: declaration of 'TT' shadows a member of 'segment_tree<Tmax, <lambda(const Tmax&, const Tmax&)> >' [-Wshadow]
   41 |     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	10 ms	10492 KB	Output is correct
3	Correct	8 ms	10416 KB	Output is correct
4	Correct	8 ms	10500 KB	Output is correct
5	Correct	8 ms	10440 KB	Output is correct
6	Correct	13 ms	10380 KB	Output is correct
7	Correct	8 ms	10416 KB	Output is correct
8	Correct	8 ms	10416 KB	Output is correct
9	Correct	9 ms	10428 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	10544 KB	Output is correct
13	Correct	9 ms	10416 KB	Output is correct
14	Correct	8 ms	10416 KB	Output is correct
15	Correct	8 ms	10492 KB	Output is correct
16	Correct	8 ms	10492 KB	Output is correct
17	Correct	8 ms	10496 KB	Output is correct
18	Correct	8 ms	10496 KB	Output is correct
19	Correct	8 ms	10416 KB	Output is correct
20	Correct	8 ms	10416 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10416 KB	Output is correct
2	Correct	11 ms	10452 KB	Output is correct
3	Correct	9 ms	10416 KB	Output is correct
4	Correct	8 ms	10404 KB	Output is correct
5	Correct	10 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	7 ms	10416 KB	Output is correct
9	Correct	8 ms	10416 KB	Output is correct
10	Correct	9 ms	10428 KB	Output is correct
11	Correct	10 ms	10492 KB	Output is correct
12	Correct	8 ms	10416 KB	Output is correct
13	Correct	8 ms	10452 KB	Output is correct
14	Correct	9 ms	10416 KB	Output is correct
15	Correct	8 ms	10416 KB	Output is correct
16	Correct	8 ms	10492 KB	Output is correct
17	Correct	8 ms	10416 KB	Output is correct
18	Correct	8 ms	10496 KB	Output is correct
19	Correct	8 ms	10416 KB	Output is correct
20	Correct	9 ms	10416 KB	Output is correct
21	Incorrect	10 ms	10416 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	311 ms	44652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	10416 KB	Output is correct
2	Correct	8 ms	10496 KB	Output is correct
3	Correct	8 ms	10436 KB	Output is correct
4	Correct	8 ms	10496 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	8 ms	10416 KB	Output is correct
9	Correct	9 ms	10416 KB	Output is correct
10	Correct	10 ms	10492 KB	Output is correct
11	Correct	11 ms	10560 KB	Output is correct
12	Correct	9 ms	10416 KB	Output is correct
13	Correct	9 ms	10416 KB	Output is correct
14	Correct	9 ms	10416 KB	Output is correct
15	Correct	12 ms	10416 KB	Output is correct
16	Correct	11 ms	10432 KB	Output is correct
17	Correct	8 ms	10416 KB	Output is correct
18	Correct	9 ms	10476 KB	Output is correct
19	Correct	8 ms	10500 KB	Output is correct
20	Correct	9 ms	10492 KB	Output is correct
21	Incorrect	11 ms	10492 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	10432 KB	Output is correct
2	Correct	8 ms	10416 KB	Output is correct
3	Correct	9 ms	10416 KB	Output is correct
4	Correct	8 ms	10416 KB	Output is correct
5	Correct	9 ms	10432 KB	Output is correct
6	Correct	9 ms	10416 KB	Output is correct
7	Correct	8 ms	10416 KB	Output is correct
8	Correct	8 ms	10500 KB	Output is correct
9	Correct	8 ms	10440 KB	Output is correct
10	Correct	8 ms	10492 KB	Output is correct
11	Correct	8 ms	10488 KB	Output is correct
12	Correct	8 ms	10440 KB	Output is correct
13	Correct	8 ms	10416 KB	Output is correct
14	Correct	9 ms	10416 KB	Output is correct
15	Correct	8 ms	10416 KB	Output is correct
16	Correct	9 ms	10416 KB	Output is correct
17	Correct	10 ms	10492 KB	Output is correct
18	Correct	8 ms	10416 KB	Output is correct
19	Correct	11 ms	10416 KB	Output is correct
20	Correct	8 ms	10416 KB	Output is correct
21	Incorrect	8 ms	10428 KB	Output isn't correct
22	Halted	0 ms	0 KB	-