제출 #760370

#제출 시각아이디문제언어결과실행 시간메모리
760370GrindMachine말 (IOI15_horses)C++17
17 / 100
90 ms20780 KiB
// Om Namah Shivaya #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; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x, y) ((x + y - 1) / (y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i, n) for(int i = 0; i < n; ++i) #define rep1(i, n) for(int i = 1; i <= n; ++i) #define rev(i, s, e) for(int i = s; i >= e; --i) #define trav(i, a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* */ const int MOD = 1e9 + 7; const int N = 5e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "horses.h" template<typename T> struct segtree { // https://codeforces.com/blog/entry/18051 /*=======================================================*/ struct data { ll a; }; data neutral = {1}; data merge(data &left, data &right) { data curr; curr.a = left.a * right.a % MOD; return curr; } void create(int i, T v) { tr[i].a = v; } void modify(int i, T v) { tr[i].a = v; } /*=======================================================*/ int n; vector<data> tr; segtree() { } segtree(int siz) { init(siz); } void init(int siz) { n = siz; tr.assign(2 * n, neutral); } void build(vector<T> &a, int siz) { rep(i, siz) create(i + n, a[i]); rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } void pupd(int i, T v) { modify(i + n, v); for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]); } data query(int l, int r) { data resl = neutral, resr = neutral; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) resl = merge(resl, tr[l++]); if (!(r & 1)) resr = merge(tr[r--], resr); } return merge(resl, resr); } }; ll n; vector<ll> a(N), b(N); segtree<ll> st(N); int get_ans(){ // { // ll ans = 0; // ll curr = 1; // rep(i,n){ // curr *= a[i]; // amax(ans, curr * b[i]); // } // return ans; // } ll prod = 1; ll point = -1; rev(i,n-1,0){ prod *= a[i]; point = i; if(prod > inf1){ break; } } ll befprod = st.query(0,point-1).a; __int128 curr = 1; __int128 best = 0; for(int i = max(point-1,0ll); i < n; ++i){ curr *= a[i]; amax(best, curr * b[i]); } ll ans = (best % MOD) * befprod % MOD; return ans; } int init(int n_, int X[], int Y[]) { n = n_; rep(i,n) a[i] = X[i], b[i] = Y[i]; rep(i,n){ st.pupd(i,a[i]); } return get_ans(); } int updateX(int pos, int val) { st.pupd(pos,val); return get_ans(); } int updateY(int pos, int val) { b[pos] = val; return get_ans(); }

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

horses.cpp: In function 'int get_ans()':
horses.cpp:149:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  149 |  rev(i,n-1,0){
      |        ~^~
horses.cpp:32:34: note: in definition of macro 'rev'
   32 | #define rev(i, s, e) for(int i = s; i >= e; --i)
      |                                  ^
horses.cpp:157:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  157 |  ll befprod = st.query(0,point-1).a;
      |                          ~~~~~^~
horses.cpp:161:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |  for(int i = max(point-1,0ll); i < n; ++i){
      |              ~~~^~~~~~~~~~~~~
horses.cpp:166:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  166 |  ll ans = (best % MOD) * befprod % MOD;
      |           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:167:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  167 |  return ans;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...