제출 #996869

#제출 시각아이디문제언어결과실행 시간메모리
996869errorgornFish 3 (JOI24_fish3)C++17
100 / 100
450 ms118964 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ii pair<int,int> #define iii tuple<int,int,int> #define fi first #define se second #define endl '\n' #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n,k,q; int arr[300005]; int brr[300005]; int pref1[300005]; int pref2[300005]; ii nxt[300005][20]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin>>n>>k; rep(x,1,n+1) cin>>arr[x]; rep(x,1,n+1) brr[x]=arr[x-1]-arr[x]; int L=1e18/k; rep(x,1,n+1) brr[x]+=(-brr[x]+k*L)%k; rep(x,1,n+1) pref1[x]=pref1[x-1]+brr[x]; rep(x,1,n+1) pref2[x]=pref2[x-1]+brr[x]*x; int P=0; vector<ii> v={{4e18,0}}; rep(x,1,n+1){ P+=brr[x]; while (!v.empty() && v.back().fi<P) v.pob(); int y=v.back().se; nxt[x][0]={y,(pref2[x]-pref2[y+1])-(pref1[x]-pref1[y+1])*(y+1)}; v.pub({P,x}); } rep(y,1,20) rep(x,1,n+1){ int u=nxt[x][y-1].fi; nxt[x][y]={ nxt[u][y-1].fi, nxt[x][y-1].se+nxt[u][y-1].se }; } cin>>q; while (q--){ int l,r; cin>>l>>r; int ans=0; rep(x,20,0) if (nxt[r][x].fi>=l){ ans+=nxt[r][x].se; r=nxt[r][x].fi; } ans+=(pref2[r]-pref2[l])-(pref1[r]-pref1[l])*(l); int v=arr[l]-(pref1[r]-pref1[l]); if (v<0) cout<<"-1"<<endl; else cout<<ans/k<<endl; } }
#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...