제출 #737910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737910		boyliguanhan	말 (IOI15_horses)	C++17	100 / 100	894 ms	92232 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace std;
using namespace __gnu_pbds;
#define LB lower_bound
#define UB upper_bound
#define P(x) pair<x,x>
#define TP(x) tuple<x,x,x>
#define V vector
#define F first
#define S second
#define TT get<2>
#define TS get<1>
#define TF get<0>
#define LE less_equal
#define GE greater_equal
#define GR greater
#define all(x) x.begin(), x.end()
#define For(i,s,n) for(int i = s; i < n; i++)
#define Forit(i,s,e) for(auto i = s; i != e; i++)
#define Rfor(i, n) for(int i = n; i>-1; i--)
#define int long long // might cause errors if problem is ioi style
#define ll long long // replacement for above if problem is ioi style
#define PB push_back
#define bll __int128_t //warning: not possible to IO a bll
#define ubll __uint128_t // IO doesn't work for ubll too
#define US unsigned
#define rbt tb_tree_tag
#define splt splay_tree_tag
#define avlt ov_tree_tag
#define ForR(i,v) for(auto i:v)
#define Tree(t, cp, tg) tree<t, null_type, cp<i>, tg, tree_order_statistics_node_update>
#define PQ priority_queue
#define mod ((int)(1e9+7))
#define rch(x) x = getchar_unlocked()
#define inf ((int)(1e18))
#define db double
#define ldb long double
#define MXN 500100 //change this value according to problem
#define MXM 200100 //change this too
int n, x[MXN], total = 1;
struct node {
    int l=0, r=0, v=v;
} seg[MXN*4];
set<int> st; 
void build(int i = 1, int l = 0, int r = MXN) {
    seg[i] = {l,r,0};
    if(l-r) build(i*2, l, l+r>>1), build(i*2+1, l+r+2>>1, r);
}
void update(int x, int v, int i = 1){
    if (seg[i].l > x || x > seg[i].r) return;
    if (seg[i].l == seg[i].r){
        seg[i].v = v;
        return;
    }
    int tm = (seg[i].l + seg[i].r) / 2;
    update(x, v, i * 2); update(x, v, i * 2 + 1);
    seg[i].v = max(seg[i * 2].v, seg[i * 2 + 1].v);
}
int query(int l, int r, int i = 1){
    if (l > seg[i].r || seg[i].l > r) return 0;
    if (l <= seg[i].l && seg[i].r <= r) return seg[i].v;
    int tm = (seg[i].l + seg[i].r) / 2;
    return max(query(l, r, i * 2), query(l, r, i * 2 + 1));
}
int inv(int x){
    int k = mod - 2, res = 1;
    while (k){
        if (k % 2) res = res * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return res;
}
int solve(){
    int res = 1, horses = 1;
    int start = 0;
    Forit (it,st.rbegin(),st.rend()){
        if (horses * x[*it] > mod) break;
        start = *it; horses *= x[*it];
    }
    int last = 0; 
    if (start) last = *(--st.LB(start));
    res = query(last, n);
    horses = 1;
    Forit (it, st.LB(start),st.end()){
        int i = *it; 
        horses *= x[i];
        int best_y = query(i, n);
        res = max(res, best_y * horses);
    }
    return res%mod*total%mod*inv(horses)%mod;
}
signed init(signed N, signed X[], signed Y[]){
    build();
    n = N;
    x[0] = 1;
    st.insert(0);
    For (i,1,N+1){
        x[i] = X[i - 1]; update(i, Y[i - 1]);
        if (x[i] == 1) continue;
        total = (total * x[i]) % mod;
        st.insert(i);
    }
    return solve();
}
signed updateX(signed pos, signed val){
    pos++;
    if (x[pos]-1){
        total = (total * inv(x[pos])) % mod;
        st.erase(pos);
    }
    x[pos] = val;
    if (x[pos]-1){
        total = (total * x[pos]) % mod;
        st.insert(pos);
    }
    return solve();
}
signed updateY(signed pos, signed  val){
    update(pos+1, val);
    return solve();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'void build(long long int, long long int, long long int)':
horses.cpp:50:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     if(l-r) build(i*2, l, l+r>>1), build(i*2+1, l+r+2>>1, r);
      |                           ~^~
horses.cpp:50:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     if(l-r) build(i*2, l, l+r>>1), build(i*2+1, l+r+2>>1, r);
      |                                                 ~~~^~
horses.cpp: In function 'void update(long long int, long long int, long long int)':
horses.cpp:52:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   52 | void update(int x, int v, int i = 1){
      |                 ^
horses.cpp:43:8: note: shadowed declaration is here
   43 | int n, x[MXN], total = 1;
      |        ^
horses.cpp:58:9: warning: unused variable 'tm' [-Wunused-variable]
   58 |     int tm = (seg[i].l + seg[i].r) / 2;
      |         ^~
horses.cpp: In function 'long long int query(long long int, long long int, long long int)':
horses.cpp:65:9: warning: unused variable 'tm' [-Wunused-variable]
   65 |     int tm = (seg[i].l + seg[i].r) / 2;
      |         ^~
horses.cpp: In function 'long long int inv(long long int)':
horses.cpp:68:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   68 | int inv(int x){
      |             ^
horses.cpp:43:8: note: shadowed declaration is here
   43 | int n, x[MXN], total = 1;
      |        ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:107:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |     return solve();
      |            ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |     return solve();
      |            ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:124:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  124 |     return solve();
      |            ~~~~~^~

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