QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#191093 | #5258. Mortgage | ucup-team902# | WA | 2ms | 10872kb | C++14 | 1.7kb | 2023-09-29 17:43:38 | 2023-09-29 17:43:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define gc c=getchar()
#define r(x) read(x)
#define ll long long
template<typename T>
inline void read(T &x){
x=0;T k=1;char gc;
while(!isdigit(c)){if(c=='-')k=-1;gc;}
while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}
const int N = 2e5 + 7;
ll a[N];
int sta[N];
int top;
vector<pair<int, int>>Q[N];
int Ans[N];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n, m; r(n), r(m);
for(int i = 1; i <= n; ++i){
r(a[i]);
}
for(int i = 1; i <= m; ++i){
int s, k; r(s), r(k);
Q[s + k - 1].push_back({s, i});
}
top = 0;
for(int i = 1; i <= n; ++i){
a[i] += a[i - 1];
while(top >= 2 && (a[i] - a[sta[top]]) * (sta[top] - sta[top - 1]) <= (a[sta[top]] - a[sta[top - 1]]) * (i - sta[top])){
--top;
}
sta[++top] = i;
for(auto &tmp : Q[i]){
int l = 1, r = top, ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(sta[mid] < tmp.first){
ans = mid;
l = mid + 1;
}
else{
r = mid - 1;
}
}
assert(sta[ans + 1] >= tmp.first);
l = ans + 1, r = top;
while(l <= r){
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if((a[sta[mid1]] - a[tmp.first - 1]) * (sta[mid2] - tmp.first + 1) <= (a[sta[mid2]] - a[tmp.first - 1]) * (sta[mid1] - tmp.first + 1)){
r = mid2 - 1;
ans = mid2;
}
else{
l = mid1 + 1;
ans = mid1;
}
}
if(a[sta[ans]] - a[tmp.first - 1] < 0) Ans[tmp.second] = -1;
else Ans[tmp.second] = (a[sta[ans]] - a[tmp.first - 1]) / (sta[ans] - tmp.first + 1);
}
}
for(int i = 1; i <= m; ++i){
if(~Ans[i]) printf("%d\n", Ans[i]);
else puts("stay with parents");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10872kb
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:
ok 10 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 9956kb
input:
1000 1000 196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...
output:
158 19 110 64 160 118 169 63 172 128 93 82 118 119 90 35 174 145 139 84 149 120 133 155 108 110 65 178 90 99 118 98 133 85 151 76 130 51 91 99 95 78 110 87 119 141 68 81 179 82 112 139 136 81 79 18 51 31 104 122 108 38 75 176 156 55 165 112 146 74 68 172 112 159 94 177 111 166 110 112 98 159 109 155...
result:
wrong answer 2nd lines differ - expected: '16', found: '19'