oj.uz

답안 #586445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586445 2022-06-30T09:26:00 Z tranxuanbach 말 (IOI15_horses) C++17
100 / 100
 355 ms 53412 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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