| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 699074 |
2023-02-15T14:31:32 Z |
jiahng |
Snowball (JOI21_ho_t2) |
C++14 |
|
677 ms |
18608 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int, int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair <pi,pi> pipi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 1000010
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0
#pragma GCC optimize("trapv")
int N,Q,w;
int pref[maxn],mnpref[maxn];
int L[maxn],R[maxn],X[maxn];
int32_t main(){
cin >> N >> Q;
FOR(i,1,N) cin >> X[i];
int mxpref=0;
FOR(i,1,Q){
cin >> w;
pref[i] = pref[i-1] + w;
mnpref[i] = min(pref[i], mnpref[i-1]);
mxpref = max(mxpref, pref[i]);
}
vpi v;
FOR(i,1,Q) v.pb(pi(mnpref[i], pref[i]));
sort(all(v));
DEC(i,v.size()-2,0) v[i].s = max(v[i].s,v[i+1].s);
L[1] = X[1] + mnpref[Q];
R[N] = X[N] + mxpref-1;
FOR(i,1,N-1){
int l = X[i]-1, r = X[i+1] + 1;
while (l+1<r){
int m = (l + r) >> 1;
auto it = upper_bound(all(v), pi(m - X[i+1], INF));
if (it != v.end() && it->s > m - X[i]) l = m;
else r = m;
}
R[i] = l; L[i+1] = max(l+1,X[i+1]+mnpref[Q]);
}
FOR(i,1,N) cout << R[i] - L[i] + 1 << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
468 KB |
Output is correct |
| 5 |
Correct |
6 ms |
468 KB |
Output is correct |
| 6 |
Correct |
5 ms |
364 KB |
Output is correct |
| 7 |
Correct |
4 ms |
468 KB |
Output is correct |
| 8 |
Correct |
4 ms |
524 KB |
Output is correct |
| 9 |
Correct |
3 ms |
508 KB |
Output is correct |
| 10 |
Correct |
3 ms |
468 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
0 ms |
308 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
6 ms |
480 KB |
Output is correct |
| 16 |
Correct |
5 ms |
468 KB |
Output is correct |
| 17 |
Correct |
4 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
308 KB |
Output is correct |
| 19 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
468 KB |
Output is correct |
| 5 |
Correct |
6 ms |
468 KB |
Output is correct |
| 6 |
Correct |
5 ms |
364 KB |
Output is correct |
| 7 |
Correct |
4 ms |
468 KB |
Output is correct |
| 8 |
Correct |
4 ms |
524 KB |
Output is correct |
| 9 |
Correct |
3 ms |
508 KB |
Output is correct |
| 10 |
Correct |
3 ms |
468 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
0 ms |
308 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
6 ms |
480 KB |
Output is correct |
| 16 |
Correct |
5 ms |
468 KB |
Output is correct |
| 17 |
Correct |
4 ms |
468 KB |
Output is correct |
| 18 |
Correct |
1 ms |
308 KB |
Output is correct |
| 19 |
Correct |
2 ms |
468 KB |
Output is correct |
| 20 |
Correct |
94 ms |
9800 KB |
Output is correct |
| 21 |
Correct |
93 ms |
9648 KB |
Output is correct |
| 22 |
Correct |
81 ms |
9416 KB |
Output is correct |
| 23 |
Correct |
86 ms |
9276 KB |
Output is correct |
| 24 |
Correct |
131 ms |
9416 KB |
Output is correct |
| 25 |
Correct |
677 ms |
16804 KB |
Output is correct |
| 26 |
Correct |
653 ms |
16644 KB |
Output is correct |
| 27 |
Correct |
599 ms |
16280 KB |
Output is correct |
| 28 |
Correct |
613 ms |
16452 KB |
Output is correct |
| 29 |
Correct |
591 ms |
16036 KB |
Output is correct |
| 30 |
Correct |
357 ms |
15284 KB |
Output is correct |
| 31 |
Correct |
175 ms |
14784 KB |
Output is correct |
| 32 |
Correct |
168 ms |
15128 KB |
Output is correct |
| 33 |
Correct |
55 ms |
2116 KB |
Output is correct |
| 34 |
Correct |
625 ms |
17160 KB |
Output is correct |
| 35 |
Correct |
601 ms |
16432 KB |
Output is correct |
| 36 |
Correct |
640 ms |
16716 KB |
Output is correct |
| 37 |
Correct |
623 ms |
16472 KB |
Output is correct |
| 38 |
Correct |
659 ms |
16304 KB |
Output is correct |
| 39 |
Correct |
671 ms |
16536 KB |
Output is correct |
| 40 |
Correct |
444 ms |
16532 KB |
Output is correct |
| 41 |
Correct |
108 ms |
10324 KB |
Output is correct |
| 42 |
Correct |
233 ms |
14856 KB |
Output is correct |
| 43 |
Correct |
385 ms |
18216 KB |
Output is correct |
| 44 |
Correct |
105 ms |
10280 KB |
Output is correct |
| 45 |
Correct |
324 ms |
16444 KB |
Output is correct |
| 46 |
Correct |
387 ms |
18336 KB |
Output is correct |
| 47 |
Correct |
431 ms |
18520 KB |
Output is correct |
| 48 |
Correct |
400 ms |
18608 KB |
Output is correct |
