제출 #1004158

#제출 시각아이디문제언어결과실행 시간메모리
1004158rahidilbayramli말 (IOI15_horses)C++17
17 / 100
72 ms17496 KiB
#include "horses.h" #pragma GCC optimize("-O3") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define ll int #define ld long double #define vl vector<ll> #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define p_b pop_back #define f first #define s second using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const ll sz = 5e5+5, mod = 1e9+7; ll a[sz], b[sz], segtree[4*sz], segtree2[4*sz], n; void build(ll v, ll l, ll r) { if(l == r) { segtree[v] = a[l]; return; } else { ll mid = (l + r) / 2; build(2*v, l, mid); build(2*v+1, mid+1, r); segtree[v] = segtree[2*v] * segtree[2*v+1]; if(segtree[v] >= mod) segtree[v] -= mod; } } void update(ll v, ll l, ll r, ll idx, ll val) { if(l == r) segtree[v] = val; else { ll mid = (l + r) / 2; if(idx <= mid) update(2*v, l, mid, idx, val); else update(2*v+1, mid+1, r, idx, val); segtree[v] = segtree[2*v] * segtree[2*v+1]; if(segtree[v] >= mod) segtree[v] -= mod; } } ll findans(ll v, ll l, ll r, ll tl, ll tr) { if(tl > tr) return 1; if(l == tl && r == tr) return segtree[v]; else { ll mid = (l + r) / 2; ll lans = findans(2*v, l, mid, tl, min(mid, tr)); ll rans = findans(2*v+1, mid+1, r, max(mid+1, tl), tr); ll f = lans * rans; if(f >= mod) f -= mod; return f; } } void build2(ll v, ll l, ll r) { if(l == r){ segtree2[v] = findans(1, 1, n, 1, l) * b[l]; if(segtree2[v] >= mod) segtree2[v] -= mod; return; } ll mid = (l + r) / 2; build2(2*v, l, mid); build2(2*v+1, mid+1, r); segtree2[v] = max(segtree2[2*v], segtree2[2*v+1]); } void update2(ll v, ll l, ll r, ll idx, ll val) { if(l == r) { segtree2[v] = findans(1, 1, n, 1, l) * val; if(segtree2[v] >= mod) segtree2[v] -= mod; return; } else { ll mid = (l + r) / 2; if(idx <= mid) update2(2*v, l, mid, idx, val); else update2(2*v+1, mid+1, r, idx, val); segtree2[v] = max(segtree2[2*v], segtree2[2*v+1]); } } ll findans2(ll v, ll l, ll r, ll tl, ll tr) { if(tl > tr) return LLONG_MIN; if(l == tl && r == tr) return segtree2[v]; else { ll mid = (l + r) / 2; ll lans = findans2(2*v, l, mid, tl, min(mid, tr)); ll rans = findans2(2*v+1, mid+1, r, max(mid+1, tl), tr); return max(lans, rans); } } ll init(ll N, ll X[], ll Y[]) { n = N; for(ll i = 1; i <= n; i++) { a[i] = X[i-1]; b[i] = Y[i-1]; } build(1, 1, n); build2(1, 1, n); return findans2(1, 1, n, 1, n) % mod; } ll updateX(ll pos, ll val) { pos++; update(1, 1, n, pos, val); return findans(1, 1, n, 1, n); } ll updateY(ll pos, ll val) { pos++; update2(1, 1, n, pos, val); return findans2(1, 1, n, 1, n); }

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

horses.cpp: In function 'int findans2(int, int, int, int, int)':
horses.cpp:108:16: warning: overflow in conversion from 'long long int' to 'int' changes value from '-9223372036854775808' to '0' [-Woverflow]
  108 |         return LLONG_MIN;
      |                ^~~~~~~~~
#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...