# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
970494 | 2024-04-26T15:54:14 Z | hariaakas646 | Snowball (JOI21_ho_t2) | C++14 | 2293 ms | 23276 KB |
#include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, j, k) for (int i = j; i < k; i++) #define frange(i, j) forr(i, 0, j) #define all(cont) cont.begin(), cont.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long int lli; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<lli> vll; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vi> vvi; typedef map<int, int> mpii; typedef set<int> seti; typedef multiset<int> mseti; typedef long double ld; void usaco() { freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin); // freopen("problem.out", "w", stdout); } int main() { // usaco(); int n, q; scd(n); scd(q); vll pos(n+2); pos[0] = -3e18; pos[n+1] = 3e18; frange(i, n) sclld(pos[i+1]); vll vec(q); frange(i, q) sclld(vec[i]); map<lli, int> po, ne; po[0] = -1; ne[0] = -1; lli tot = 0; frange(i, q) { tot += vec[i]; if(tot >= 0) { if(po.find(tot) == po.end()) po[tot] = i; } else { if(ne.find(abs(tot)) == ne.end()) ne[abs(tot)] = i; } } int mi = 1e9; auto it = po.end(); while(it != po.begin()) { it--; lli v = (*it).f; mi = min(mi, (*it).s); po[v] = mi; it = po.find(v); } it = ne.end(); mi = 1e9; while(it != ne.begin()) { it--; lli v = (*it).f; mi = min(mi, (*it).s); ne[v] = mi; it = ne.find(v); } forr(i, 1, n+1) { lli lo = pos[i-1]; lli hi = pos[i]; while(lo != hi) { lli mid = lo+(hi-lo)/2; lli pv = mid - pos[i-1]; lli nv = pos[i] - mid; auto it = po.lower_bound(pv+1); int v1 = 1e9; if(it != po.end()) { v1 = (*it).s; } it = ne.lower_bound(nv); int v2 = 1e9; if(it != ne.end()) { v2 = (*it).s; } if(v2 < v1) { hi = mid; } else { lo = mid+1; } } lli l = lo; lo = pos[i]; hi = pos[i+1]; while(lo != hi) { lli mid = lo+(hi-lo+1)/2; lli pv = mid - pos[i]; lli nv = pos[i+1] - mid; auto it = po.lower_bound(pv); int v1 = 1e9; if(it != po.end()) { v1 = (*it).s; } it = ne.lower_bound(nv+1); int v2 = 1e9; if(it != ne.end()) { v2 = (*it).s; } if(v1 < v2) { lo = mid; } else { hi = mid-1; } } lli r = lo; printf("%lld\n", r-l); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 2 ms | 344 KB | Output is correct |
4 | Correct | 8 ms | 600 KB | Output is correct |
5 | Correct | 8 ms | 600 KB | Output is correct |
6 | Correct | 7 ms | 348 KB | Output is correct |
7 | Correct | 6 ms | 604 KB | Output is correct |
8 | Correct | 5 ms | 604 KB | Output is correct |
9 | Correct | 4 ms | 444 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 600 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 9 ms | 604 KB | Output is correct |
16 | Correct | 8 ms | 604 KB | Output is correct |
17 | Correct | 4 ms | 604 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 2 ms | 344 KB | Output is correct |
4 | Correct | 8 ms | 600 KB | Output is correct |
5 | Correct | 8 ms | 600 KB | Output is correct |
6 | Correct | 7 ms | 348 KB | Output is correct |
7 | Correct | 6 ms | 604 KB | Output is correct |
8 | Correct | 5 ms | 604 KB | Output is correct |
9 | Correct | 4 ms | 444 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 600 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 9 ms | 604 KB | Output is correct |
16 | Correct | 8 ms | 604 KB | Output is correct |
17 | Correct | 4 ms | 604 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 70 ms | 16644 KB | Output is correct |
21 | Correct | 71 ms | 16208 KB | Output is correct |
22 | Correct | 70 ms | 16212 KB | Output is correct |
23 | Correct | 94 ms | 16212 KB | Output is correct |
24 | Correct | 286 ms | 16448 KB | Output is correct |
25 | Correct | 1955 ms | 21244 KB | Output is correct |
26 | Correct | 1880 ms | 21008 KB | Output is correct |
27 | Correct | 1782 ms | 19932 KB | Output is correct |
28 | Correct | 1629 ms | 18784 KB | Output is correct |
29 | Correct | 1328 ms | 13664 KB | Output is correct |
30 | Correct | 344 ms | 7528 KB | Output is correct |
31 | Correct | 59 ms | 6740 KB | Output is correct |
32 | Correct | 50 ms | 7220 KB | Output is correct |
33 | Correct | 125 ms | 2436 KB | Output is correct |
34 | Correct | 1991 ms | 21532 KB | Output is correct |
35 | Correct | 1851 ms | 19772 KB | Output is correct |
36 | Correct | 2293 ms | 21228 KB | Output is correct |
37 | Correct | 1946 ms | 19924 KB | Output is correct |
38 | Correct | 2045 ms | 19592 KB | Output is correct |
39 | Correct | 1896 ms | 19888 KB | Output is correct |
40 | Correct | 536 ms | 19908 KB | Output is correct |
41 | Correct | 139 ms | 17252 KB | Output is correct |
42 | Correct | 75 ms | 7088 KB | Output is correct |
43 | Correct | 741 ms | 22972 KB | Output is correct |
44 | Correct | 123 ms | 16928 KB | Output is correct |
45 | Correct | 923 ms | 19932 KB | Output is correct |
46 | Correct | 1103 ms | 23180 KB | Output is correct |
47 | Correct | 373 ms | 14928 KB | Output is correct |
48 | Correct | 539 ms | 23276 KB | Output is correct |