| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 928636 |
2024-02-16T23:11:17 Z |
AdamGS |
Dungeon 3 (JOI21_ho_t5) |
C++17 |
|
293 ms |
82224 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=2e5+7;
ll A[LIM], B[LIM], lewo[LIM], prawo[LIM], wynik[LIM], indl[LIM], indr[LIM], trma[4*LIM], N=1;
vector<pair<pair<ll,ll>,pair<ll,ll>>>V;
vector<int>L[LIM], R[LIM];
pair<pair<ll,ll>,ll>pyt[LIM];
pair<ll,ll>tr[4*LIM];
pair<ll,ll>dodaj(pair<ll,ll>a, pair<ll,ll>b) {
return {a.st+b.st, a.nd+b.nd};
}
void upd(int v, pair<ll,ll>x) {
v+=N;
while(v) {
tr[v]=dodaj(tr[v], x);
v/=2;
}
}
pair<ll,ll>cnt(int l, int r) {
l+=N; r+=N;
pair<ll,ll>ans=tr[l];
if(l!=r) ans=dodaj(ans, tr[r]);
while(l/2!=r/2) {
if(l%2==0) ans=dodaj(ans, tr[l+1]);
if(r%2==1) ans=dodaj(ans, tr[r-1]);
l/=2; r/=2;
}
return ans;
}
ll cntma(int l, int r) {
l+=N; r+=N;
ll ans=max(trma[l], trma[r]);
while(l/2!=r/2) {
if(l%2==0) ans=max(ans, trma[l+1]);
if(r%2==1) ans=max(ans, trma[r-1]);
l/=2; r/=2;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
while(N<=n+3) N*=2;
A[1]=INF;
rep(i, n) {
cin >> A[i+2];
A[i+2]+=A[i+1];
}
rep(i, n) {
cin >> B[i+1];
trma[N+i+1]=B[i+1];
}
vector<int>S;
rep(i, n+2) {
while(S.size() && B[S.back()]>B[i]) S.pop_back();
if(S.size()) lewo[i]=S.back();
S.pb(i);
}
S.clear();
for(int i=n+1; i>=0; --i) {
while(S.size() && B[S.back()]>=B[i]) S.pop_back();
if(S.size()) prawo[i]=S.back(); else prawo[i]=n-1;
S.pb(i);
}
rep(i, m) {
cin >> pyt[i].st.st >> pyt[i].st.nd >> pyt[i].nd;
L[pyt[i].st.st].pb(i);
R[pyt[i].st.nd].pb(i);
}
S.clear();
vector<ll>pref;
for(int i=n+1; i; --i) {
while(S.size() && B[S.back()]>=B[i]) {
S.pop_back();
pref.pop_back();
}
if(S.size()) pref.pb(B[i]*(A[S.back()]-A[i])+pref.back());
else pref.pb(0);
S.pb(i);
for(auto j : L[i]) {
int po=0, ko=(int)S.size()-1;
while(po<ko) {
int sr=(po+ko)/2;
if(A[S[sr]]<=min(A[i]+pyt[j].nd, A[pyt[j].st.nd])) ko=sr; else po=sr+1;
}
wynik[j]+=pref.back()-pref[po];
wynik[j]+=B[S[po]]*min(min(A[prawo[S[po]]], A[pyt[j].st.nd])-A[S[po]], pyt[j].nd);
indl[j]=S[po]+1;
// to usunac
indr[j]=pyt[j].st.nd-1;
}
}
for(int i=1; i<=n; ++i) {
V.pb({{A[i]-A[lewo[i]], -i}, {(A[i]-A[lewo[i]])*B[i], -B[i]}});
V.pb({{A[prawo[i]]-A[i], -i}, {(A[prawo[i]]-A[i])*B[i], -B[i]}});
V.pb({{A[prawo[i]]-A[lewo[i]], -i}, {(A[lewo[i]]-A[prawo[i]])*B[i], B[i]}});
tr[N+i]={0, B[i]};
}
for(int i=N-1; i; --i) {
tr[i]=dodaj(tr[2*i], tr[2*i+1]);
trma[i]=max(trma[2*i], trma[2*i+1]);
}
rep(i, m) if(indl[i]<=indr[i]) V.pb({{pyt[i].nd, i}, {indl[i], indr[i]}});
sort(all(V));
for(auto i : V) {
if(i.st.nd<0) upd(-i.st.nd, i.nd);
else {
pair<ll,ll>x=cnt(i.nd.st, i.nd.nd);
wynik[i.st.nd]+=x.st+x.nd*i.st.st;
}
}
rep(i, m) if(cntma(pyt[i].st.st, pyt[i].st.nd-1)>pyt[i].nd) wynik[i]=-1;
rep(i, m) cout << wynik[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
25824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
41676 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
40652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
293 ms |
82224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
25824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
