QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#327945 | #5258. Mortgage | Terdy | WA | 6ms | 22896kb | C++14 | 1.9kb | 2024-02-15 15:40:57 | 2024-02-15 15:40:57 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
# define int long long
# define PII pair< int , int >
# define MP make_pair
# define fi first
# define se second
const int N = 2e5 + 5;
int n , m , a[N];
vector< PII > operator + (vector< PII > a , vector< PII > b)
{
vector< PII > c = a;
for(auto t : b)
{
int siz = c.size();
while(siz >= 2 && 1ll * (t.se - c[siz - 1].se) * (t.fi - c[siz - 2].fi) < 1ll * (t.se - c[siz - 2].se) * (t.fi - c[siz - 1].fi)) c.pop_back() , siz--;
c.push_back(t);
}
return c;
}
struct Seg
{
vector< PII > vec[N<<2];
# define lc x << 1
# define rc x << 1 | 1
# define mid (l + r >> 1)
void PushUp(int x) {vec[x] = vec[lc] + vec[rc];}
void Build(int x , int l , int r)
{
if(l == r) return vec[x].emplace_back(l , a[l]) , void();
Build(lc , l , mid) , Build(rc , mid + 1 , r);
PushUp(x);
}
vector< PII > Query(int x , int l , int r , int L , int R)
{
if(L <= l && r <= R) return vec[x];
if(mid < L) return Query(rc , mid + 1 , r , L , R);
if(mid >= R) return Query(lc , l , mid , L , R);
return Query(lc , l , mid , L , R) + Query(rc , mid + 1 , r , L , R);
}
} tr;
signed main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i] , a[i] += a[i - 1];
tr.Build(1 , 1 , n);
for(int i = 1; i <= m; i++)
{
int s , t , l , r , ans;
cin >> s >> t , t = s + t - 1;
vector< PII > vec = tr.Query(1 , 1 , n , s , t);
// for(auto t : vec) cout << t.fi << ' ' << t.se << endl;
l = 0 , r = vec.size() - 1;
if(vec.size() == 1) cout << '*';
while(l <= r)
{
if(mid == 0) {ans = 0 , l = 1; continue ;}
if(1ll * (vec[mid].se - a[s - 1]) * (vec[mid - 1].fi - s + 1) <= 1ll * (vec[mid - 1].se - a[s - 1]) * (vec[mid].fi - s + 1)) ans = mid , l = mid + 1;
else r = mid - 1;
}
ans = (vec[ans].se - a[s - 1]) / (vec[ans].fi - s + 1);
if(ans < 0) cout << "stay with parents\n";
else cout << ans << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 22896kb
input:
10 10 21 18 19 18 16 15 13 13 13 10 10 1 6 4 7 3 2 2 6 5 2 6 3 2 4 1 1 5 6 3
output:
*10 13 13 18 12 16 18 *18 18 13
result:
wrong answer 1st lines differ - expected: '10', found: '*10'