제출 #1103788

#제출 시각아이디문제언어결과실행 시간메모리
1103788hahahoang132Fish 3 (JOI24_fish3)C++17
0 / 100
388 ms49004 KiB
//ahussssssssssss #include<bits/stdc++.h> using namespace std; #define ll long long #define bit(x,y) ((x >> y) & 1LL) const ll N = 3e5 + 5; const ll mod = 1e9 + 7; const ll inf = LLONG_MAX/4; struct segtree { ll n; ll b[N * 4],sz[N * 4],lz[N * 4]; void build(ll n) { this->n = n; build(0,1,n); } void build(ll x, ll l, ll r) { if(l == r) { b[x] = lz[x] = 0; sz[x] = 1; }else { ll mid = (l + r) / 2; build(x * 2 + 1,l,mid); build(x * 2 + 2,mid + 1,r); sz[x] = sz[x * 2 + 1] + sz[x * 2 + 2]; } } void udt(ll l, ll r, ll add) { udt(0,1,n,l,r,add); } void push(ll x) { ll x1 = x * 2 + 1; ll x2 = x1 + 1; b[x1] += lz[x] * sz[x1]; b[x2] += lz[x] * sz[x2]; lz[x1] += lz[x]; lz[x2] += lz[x]; lz[x] = 0; } void udt(ll x, ll l, ll r, ll s, ll e, ll add) { if(e < l || r < s) return; if(s <= l && r <= e) { b[x] += sz[x] * add; lz[x] += add; return; } push(x); ll mid = (l + r) / 2; udt(x * 2 + 1,l,mid,s,e,add); udt(x * 2 + 2,mid + 1,r,s,e,add); b[x] = b[x * 2 + 1] + b[x * 2 + 2]; } ll get(ll x) { return get(x,x); } ll get(ll l, ll r) { return get(0,1,n,l,r); } ll get(ll x, ll l, ll r, ll s, ll e) { if(e < l || r < s) return 0; if(s <= l && r <= e) return b[x]; push(x); ll mid = (l + r) / 2; return get(x * 2 + 1,l,mid,s,e) + get(x * 2 + 2,mid + 1,r,s,e); } }; segtree f; ll a[N]; vector<pair<ll,ll>> qr[N]; ll ans[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n,d; cin >> n >> d; f.build(n); ll i,j; for(i = 1;i <= n;i++) { cin >> a[i]; } ll q; cin >> q; for(i = 1;i <= q;i++) { ll l,r; cin >> l >> r; qr[r].push_back({l,i}); } vector<pair<ll,ll>> sus; for(i = 1;i <= n;i++) { ll hehe = i; while(!sus.empty()) { ll s = sus.back().first; ll e = sus.back().second; sus.pop_back(); ll t1 = a[e] - d * f.get(e); ll t2 = a[e + 1] - d * f.get(e + 1); if(t1 <= t2) break; ll t = t1 - t2; ll add = t / d; if(t % d != 0) add++; f.udt(s,e,add); hehe = s; } sus.push_back({hehe,i}); for(auto tmp : qr[i]) { if(d * f.get(tmp.first) > a[tmp.first]) ans[tmp.second] = -1; else ans[tmp.second] = f.get(tmp.first,i); } } for(i = 1;i <= q;i++) cout << ans[i] << "\n"; }

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

Main.cpp: In function 'int main()':
Main.cpp:89:10: warning: unused variable 'j' [-Wunused-variable]
   89 |     ll i,j;
      |          ^
#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...